Advertisement
yicongli

LG5283

Apr 10th, 2019
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     T k=1;char gc;x=0;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c))x=x*10+c-'0',gc;x*=k;
  14. }
  15.  
  16. const int N=5e5+7;
  17. const int D=2;
  18.  
  19. ll a[N];
  20. int tot=1,root;
  21.  
  22. int ch[N*30][2];
  23. int siz[N*30];
  24.  
  25. inline void insert(ll x){
  26.     int rt=1;
  27.     ++siz[rt];
  28.     for(ll i=32;~i;--i){
  29.         if(!ch[rt][x>>i&1])ch[rt][x>>i&1]=++tot;
  30.         rt=ch[rt][x>>i&1];
  31.         ++siz[rt];
  32.     }
  33. }
  34.  
  35. inline ll query(ll x,int k){
  36.     int rt=1;
  37.     ll ret=0;
  38.     k=siz[1]-k+1;
  39.     for(ll i=32;~i;--i){
  40.         if(siz[ch[rt][(x>>i&1)]]<k){
  41.             k-=siz[ch[rt][x>>i&1]];
  42.             rt=ch[rt][(x>>i&1)^1];
  43.             ret|=(1ll<<i);
  44.         }
  45.         else {
  46.             rt=ch[rt][x>>i&1];
  47.         }
  48.     }
  49.     return ret;
  50. }
  51.  
  52. struct Data{
  53.     ll x;
  54.     int id,rk;
  55.  
  56.     inline bool operator < (const Data &a)const{
  57.         return x<a.x;
  58.     }
  59. };
  60.  
  61. int main(){
  62.     // freopen("xor.in","r",stdin);
  63.     // freopen("xor.out","w",stdout);
  64.     int n,k;r(n),r(k);
  65.     for(int i=1;i<=n;++i){
  66.         r(a[i]);
  67.         a[i]^=a[i-1];
  68.     }
  69.     for(int i=0;i<=n;++i){
  70.         insert(a[i]);
  71.     }
  72.     priority_queue<Data>Q;
  73.     for(int i=0;i<=n;++i){
  74.         Q.push(Data{query(a[i],1),i,1});
  75.     }
  76.     k*=2;
  77.     ll ans=0;
  78.     for(int i=1;i<=k;++i){
  79.         Data T=Q.top();Q.pop();
  80.         if(i&1)ans+=T.x;
  81.         Q.push(Data{query(a[T.id],T.rk+1),T.id,T.rk+1});
  82.     }
  83.     printf("%lld\n",ans);
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement