求助
查看原帖
求助
800499
suzhikz楼主2024/12/13 16:37

每个答案都很接近但是就是错的

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
#define int long long
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
//void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=5e5+5;
ll n,m,a[N];
int ch[N*36][2],cnt[N*36],tot,rt[N]; 
void ins(int x1,int x2,int pos,int w){
	if(pos<0)return ;
	int tmp=(w>>pos)&1;
	ch[x1][!tmp]=ch[x2][!tmp];
	ch[x1][tmp]=++tot;
	cnt[ch[x1][tmp]]=cnt[ch[x2][tmp]]+1;
	ins(ch[x1][tmp],ch[x2][tmp],pos-1,w);
}
void build(){
	for(int i=1;i<=n;i++){
		rt[i]=++tot;ins(rt[i],rt[i-1],33,a[i]);
	}
}
ll query(int x1,int x2,int pos,int w,int k){
	if(pos<0)return 0;
	int tmp=(w>>pos)&1;
	if(cnt[ch[x2][tmp]]-cnt[ch[x1][tmp]]>=k){
		return query(ch[x1][tmp],ch[x2][tmp],pos-1,w,k);
	}else{
		return (1ll<<pos)+query(ch[x1][!tmp],ch[x2][!tmp],pos-1,w,k-(cnt[ch[x2][tmp]]-cnt[ch[x1][tmp]]));
	}
}
struct node{
	ll id,rank,w;
	friend bool operator<(node a,node b){
		return a.w<b.w;
	}
};
priority_queue<node>q;
signed main(){
	read(n);read(m);
	for(int i=1;i<=n;i++){
		read(a[i]);a[i]^=a[i-1];
	}
	rt[0]=++tot;ins(0,rt[0],33,0);
	build();
	node book;
	for(int i=1;i<=n;i++){
		book.rank=n;book.id=i;book.w=query(rt[0],rt[n],33,a[i],n);q.push(book);
	}
	m*=2;
	ll ans=0;
	while(m--){
   // cout<<ans<<endl;
		book=q.top();ans+=book.w;book.rank--;
		book.w=query(rt[0],rt[n],33,a[book.id],book.rank-1);
		q.push(book);
	}
	cout<<ans/2;
	return 0;
}

2024/12/13 16:37
加载中...