P5283

看的第一篇题解

样例过了

调了一坤时了

呃。呃。呃。

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct Node{
	int id,rank,val;
	friend bool operator < (Node a,Node b){
		return a.val < b.val;
	}
};
priority_queue<Node> q;
int tot,nxt[10000006][2],siz[10000006],n,k,a[500006],dis[500006];
void add(int x){
	int p = 1;
	siz[p]++;
	for(int i = 32;i >= 0; i--){
		int o = (x>>i)&1;
		if(!nxt[p][o])
			nxt[p][o] = ++tot;
		p = nxt[p][o];
		siz[p]++;                                                                                                                                                                                                                                                                                                                                                               
	}
}
int query(int x,int id){
	int p = 1,ans = 0;
	for(int i = 32;i >= 0; i--){
		int o = ((x>>i)&1)^1;
		if(nxt[p][o]&&id <= siz[nxt[p][o]]){
			ans += (1ll<<i);
			p = nxt[p][o];
		}else{
			p = nxt[p][o^1];
			id -= siz[p];
		}
	}
	return ans;
}
main(){
	tot = 1;
	cin >> n >> k;
	add(0);
	for(int i = 1;i <= n; i++){
		cin >> a[i];
		dis[i] = dis[i-1]^a[i];
		add(dis[i]);
	}
	for(int i = 1;i <= n; i++)
		q.push({i,1,query(dis[i],1)});
	int ans = 0;
	for(int i = 1;i <= 2*k; i++){
		Node o = q.top();
		q.pop();
		ans += o.val;
		if(o.rank < n) q.push({o.id,o.rank+1,query(o.id,o.rank+1)});
	}
	cout << ans/2;
	return 0;
}