F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 5495 >> 无故ce求解
ltsb1 @ 2019-08-09 20:16:34
[ Quote ] [ Edit ] [ Delete ] 1#
以下是我的代码:
#include<bits/stdc++.h>
using namespace std;
#define N 500010
typedef unsigned int ui;
ui n,k,a[N],ct,nc,sz[N<<6],tw[N],s[N];
int c[N<<6][2],d[N][35],rt[N];
long long ans;
void ins(int p,int &o,int x,int t){
if(!o)o=++nc;
sz[o]=sz[p]+1;
if(x>32)return;
c[o][!d[t][x]]=c[p][!d[t][x]];
ins(c[p][d[t][x]],c[o][d[t][x]],x+1,t);
}
ui q(int o,int k,int x,int t){
if(x>32)return 0ll;
int a=c[o][!d[t][x]],b=c[o][d[t][x]];
if(!a)return q(b,k,x+1,t);
else if(!b)return q(a,k,x+1,t)+tw[32-x];
else{
if(sz[a]>=k)return q(a,k,x+1,t)+tw[32-x];
return q(b,k-sz[a],x+1,t);
}
}
struct no{
ui va;
int k,po;
bool operator <(const no &rhs)const{
return va<rhs.va;
}
};
priority_queue<no>pq;
int main(){
scanf("%u%u",&n,&k);
tw[0]=1;
for(int i=1;i<=32;i++)
tw[i]=tw[i-1]*2ll;
for(int i=1;i<=n;i++){
scanf("%u",&a[i]);
s[i]=s[i-1]^a[i];
}
for(int i=1;i<=n;i++){
ui x=s[i];
ct=0;
while(x){
d[i][++ct]=x&1;
x/=2;
}
reverse(d[i]+1,d[i]+33);
ins(rt[i-1],rt[i],1,i-1);
}
for(int i=1;i<=n;i++)
pq.push((no){q(rt[i],1,1,i),1,i});
for(int i=1;i<=k;i++){
no x=pq.top();pq.pop();
ans+=x.va;
if(x.k<x.po)pq.push((no){q(rt[x.po],x.k+1,1,x.po),x.k+1,x.po});
}
printf("%lld",ans);
}
ltsb1 @ 2019-08-09 20:17:34
[ Quote ] [ Edit ] [ Delete ] 2#
在luogu已经ac
[Top] [Previous Page] [Next Page]

HOME Back