记录编号	593302	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2019]异或粽子	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	7.151 s
提交时间	2024-08-29 17:30:44	内存使用	83.89 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define in inline
#define se second
#define mp make_pair
#define pb push_back
const int N = 5e5+10;

ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}


int n,k;
int s[N],root[N];
struct Trie{
	struct node{int son[2];}s[N*40];
	int siz[N*40],cnt;
	void insert(int z,int id){
		int now = ++cnt,la = id ? root[id-1] : 0;
		root[id] = now;
		s[now] = s[la];
		siz[now] = siz[la] + 1;
		for(int i = 31;i >= 0;i--){
			int v = z >> i & 1;
			s[now].son[v] = ++cnt;
			now = cnt,la = s[la].son[v];
			s[now] = s[la];
			siz[now] = siz[la] + 1;
		}
	}
	ll ask(int r,int z,int k){
		ll ans = 0,p = root[r];
		for(int i = 31;i >= 0;i--){
			int v = z >> i & 1;
			int now = s[p].son[v ^ 1];
			if(now){
				if(siz[now] >= k)ans += (1ll << i),p = now;
				else k -= siz[now],p = s[p].son[v];
			}
			else p = s[p].son[v];
		}
		return ans;
	}
}Tr;

struct made{
	ll z;int id,k;
	bool operator < (made a)const{
		return z == a.z ? id > a.id : z < a.z;
	}
};
priority_queue<made,vector<made>>q;
int main(){
	freopen("haoi2019_xor.in","r",stdin);
	freopen("haoi2019_xor.out","w",stdout);
	n = read(),k = read();
	Tr.insert(0,0);
	for(int i = 1;i <= n;i++){
		s[i] = s[i-1] ^ read();
		Tr.insert(s[i],i);
	}
	for(int i = 1;i <= n;i++)q.push({Tr.ask(i,s[i],1),i,1});
	ll ans = 0;
	for(int i = 1;i <= k;i++){
		made now = q.top();q.pop();
		ans += (ll)now.z;
		if(++now.k <= now.id)q.push({Tr.ask(now.id,s[now.id],now.k),now.id,now.k});
	}
	printf("%lld\n",ans);

	return 0;

}