Trie 35pts
查看原帖
Trie 35pts
289296
zymooll楼主2023/4/25 14:05
// Author:zymooll

#include<bits/stdc++.h>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define int long long
using namespace std;
int read(){
	int s=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=s*10+c-'0';
		c=getchar();
	}
	return s*w;
}
void print(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>=10)print(x/10);
	putchar(x%10+'0');
	return;
}
const int sd=31;
int n,k,ansl;
int a[500010];
int cnt;
struct Tree{
	int cnt,son[2];
}t[16000010];
struct Node{
	int w,x,y;
	friend bool operator < (Node aa,Node bb){
		return aa.w<bb.w;
	}
};
priority_queue<Node>q;
void insert(int num){
	int u=0;
	for(int i=sd;i>=0;i--){
		int ls=(num>>i)&1;
		if(!t[u].son[ls])t[u].son[ls]=++cnt;
		u=t[u].son[ls];
		t[u].cnt++;
	}
}
int find(int num,int p){
	int pp=p;
	int ans=0,u=0;
	for(int i=sd;i>=0;i--){
		int ls=(num>>i)&1;
		if(t[t[u].son[ls^1]].cnt>=pp){
			ans|=(1ll<<i);
			u=t[u].son[ls^1];
		}
		else{
			pp-=t[t[u].son[ls^1]].cnt;
			u=t[u].son[ls];
		}
	}
	return ans;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		a[i]^=a[i-1];
	}
	for(int i=1;i<=n;i++){
		insert(a[i]);
	}
	for(int i=1;i<=n;i++){
		q.push((Node){find(a[i],1),i,1});
	}
	for(int i=1;i<=k*2;i++){
		Node ls=q.top();
		q.pop();
		ansl+=ls.w;
		q.push((Node){find(a[ls.x],ls.y+1),ls.x,ls.y+1});
	}
	print(ansl/2);
	return 0;
}

2023/4/25 14:05
加载中...