【悬赏1关注】萌新可持久化trie WA 0pts求调
查看原帖
【悬赏1关注】萌新可持久化trie WA 0pts求调
743811
Shakespeare07楼主2023/5/16 19:07
#include<bits/stdc++.h>
using namespace std;

#define int long long

int read(){
	int s=0,w=1; char c=getchar();
	while(!isdigit(c)){ if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)){ s=(s<<3)+(s<<1)+(c^48); c=getchar();}
	return s*w;
}

const int N=1e6+5;

int n,k,sum[N],rt[N],tot,ch[N*32][2],la[N*32];

struct node{
	int val,l,r,o,t;
	node(){}
	node(int _val,int _l,int _r,int _o,int _t){
		val=_val,l=_l,r=_r,o=_o,t=_t;
	}
};
bool operator < (node p,node pp){
	return p.val<pp.val;
}
priority_queue<node> q;

void ins(int a,int b,int c,int x){
	if(c<0) return la[a]=x,void();
	int i=((sum[x]>>c)&1);
	ch[a][!i]=ch[b][!i];
	ch[a][i]=++tot;
	ins(ch[a][i],ch[b][i],c-1,x);
	la[a]=max(la[ch[a][i]],la[ch[a][!i]]);
}
int query(int a,int b,int c,int x){
	if(c<0) return la[a];
	int i=((x>>c)&1);
	return query(ch[a][i^(la[ch[a][i^1]>=b])],b,c-1,x);
}

signed main(){
	n=read(),k=read();
	la[0]=-1;
	rt[0]=++tot;
	ins(rt[0],0,31,0);
	for(int i=1;i<=n;++i){
		int x=read();
		sum[i]=(sum[i-1]^x);
		rt[i]=++tot;
		ins(rt[i],rt[i-1],31,i);
		int j=query(rt[i-1],0,31,sum[i]);
		q.push(node(sum[i]^sum[j],0,i-1,i,j));
	}
	
	int res=0;
	while(k--){
		node tmp=q.top();
		q.pop();
		res+=tmp.val;
		if(tmp.l<=tmp.t-1){
			int j=query(rt[tmp.t-1],tmp.l,31,sum[tmp.o]);
			q.push(node(sum[tmp.o]^sum[j],tmp.l,tmp.t-1,tmp.o,j));
		}
		if(tmp.t+1<=tmp.r){
			int j=query(rt[tmp.r],tmp.t+1,31,sum[tmp.o]);
			q.push(node(sum[tmp.o]^sum[j],tmp.t+1,tmp.r,tmp.o,j));
		}
	}
	cout<<res<<endl;
	
	return 0;
}
2023/5/16 19:07
加载中...