WA #60pts 求调
查看原帖
WA #60pts 求调
1013479
lyx128楼主2024/11/10 19:54
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5;

ll n,k;
ll a[N+5];
ll sum[N+5];

ll ch[N*50+5][2];
ll cnt[N+5];
ll tot;
struct ZongZi{
	ll val;
	ll id,kth;
	bool operator <(ZongZi b) const{
		return val<b.val;
	}
}b[N+5];
priority_queue<ZongZi> q;

void insert(ll x){
	ll u=0;
	for(ll i=32;i>=0;i--){
		ll t=(x>>i)&1ll;
		if(!ch[u][t])
			ch[u][t]=++tot;
		u=ch[u][t];
		cnt[u]++;
	}
	return ;
}
ll query(ll x,ll kth){
	ll res=0;
	ll u=0;
	for(ll i=32;i>=0;i--){
		ll t=(x>>i)&1ll;
		if(cnt[ch[u][t^1ll]]>=kth){
			u=ch[u][t^1ll];
			res+=(1ll<<i);
		}
		else{
			kth-=cnt[ch[u][t^1ll]];
			u=ch[u][t];
		}
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1ll]^a[i];
	}
	for(ll i=0;i<=n;i++)
		insert(sum[i]);
	for(ll i=0;i<=n;i++){
		b[i].id=i;
		b[i].kth=1;
		b[i].val=query(sum[i],1ll);
		q.push(b[i]);
	}
	ll ans=0;
	k*=2;
	for(ll i=1;i<=k;i++){
		ZongZi u=q.top();
		q.pop();
		ans+=u.val;
		b[u.id].kth++;
		b[u.id].val=query(sum[u.id],b[u.id].kth);
		q.push(b[u.id]);
	}
	ans/=2;
	cout<<ans<<"\n";
	return 0;
}
2024/11/10 19:54
加载中...