Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll long long
- template<typename T>
- inline void read(T&x){
- T k=1;char gc;x=0;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c))x=x*10+c-'0',gc;x*=k;
- }
- const int N=5e5+7;
- const int D=2;
- ll a[N];
- int tot=1,root;
- int ch[N*30][2];
- int siz[N*30];
- inline void insert(ll x){
- int rt=1;
- ++siz[rt];
- for(ll i=32;~i;--i){
- if(!ch[rt][x>>i&1])ch[rt][x>>i&1]=++tot;
- rt=ch[rt][x>>i&1];
- ++siz[rt];
- }
- }
- inline ll query(ll x,int k){
- int rt=1;
- ll ret=0;
- k=siz[1]-k+1;
- for(ll i=32;~i;--i){
- if(siz[ch[rt][(x>>i&1)]]<k){
- k-=siz[ch[rt][x>>i&1]];
- rt=ch[rt][(x>>i&1)^1];
- ret|=(1ll<<i);
- }
- else {
- rt=ch[rt][x>>i&1];
- }
- }
- return ret;
- }
- struct Data{
- ll x;
- int id,rk;
- inline bool operator < (const Data &a)const{
- return x<a.x;
- }
- };
- int main(){
- // freopen("xor.in","r",stdin);
- // freopen("xor.out","w",stdout);
- int n,k;r(n),r(k);
- for(int i=1;i<=n;++i){
- r(a[i]);
- a[i]^=a[i-1];
- }
- for(int i=0;i<=n;++i){
- insert(a[i]);
- }
- priority_queue<Data>Q;
- for(int i=0;i<=n;++i){
- Q.push(Data{query(a[i],1),i,1});
- }
- k*=2;
- ll ans=0;
- for(int i=1;i<=k;++i){
- Data T=Q.top();Q.pop();
- if(i&1)ans+=T.x;
- Q.push(Data{query(a[T.id],T.rk+1),T.id,T.rk+1});
- }
- printf("%lld\n",ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement