P5283 [十二省联考2019]异或粽子

链接

类似于权值线段树查询区间 (k) 大值。。。（写复杂了。。。

#include<bits/stdc++.h>
#define IL inline
#define LL unsigned int
using namespace std;
const int N=5e5+3;
int n,m,k,cnt,c1,c2,rt[N],ch[N*40][2],sum[N*40],pos[N];
LL a[N];
long long ans;
IL LL in(){
  char c;
  while((c=getchar())<'0'||c>'9');
  LL x=c-'0';
  while((c=getchar())>='0'&&c<='9')
    x=x*10+c-'0';
  return x;
}
void upd(int &o,int p,LL x,int dep){
  o=++cnt,ch[o][0]=ch[p][0],ch[o][1]=ch[p][1],sum[o]=sum[p]+1;
  if(dep==-1) return;
  int op=x>>dep&1;
  upd(ch[o][op],ch[p][op],x,dep-1);
}
void calc(int o,LL x,int dep){
  if(!o||dep==-1) return;
  int op=x>>dep&1;
  ans+=1ll*sum[ch[o][op^1]]*(1ull<<dep);
  calc(ch[o][0],x,dep-1),calc(ch[o][1],x,dep-1);
}
int main()
{
	n=in(),k=in();
	for(int i=1;i<=n;++i) a[i]=in()^a[i-1];
	upd(rt[0],rt[0],0,31);
	for(int i=1;i<=n;++i) upd(rt[i],rt[i-1],a[i],31);
	for(int i=1;i<=n;++i) pos[i]=rt[i-1];
	for(int i=31;~i;--i){
		LL res=0;
	  for(int j=1;j<=n;++j) res+=sum[ch[pos[j]][(a[j]>>i&1)^1]];
		if(res<=k){
			for(int j=1;j<=n;++j) calc(ch[pos[j]][(a[j]>>i&1)^1],a[j],i-1);
		  for(int j=1;j<=n;++j) pos[j]=ch[pos[j]][a[j]>>i&1];
		  ans+=1ll*res*(1ull<<i),k-=res;
		}
		else{
		  for(int j=1;j<=n;++j) pos[j]=ch[pos[j]][(a[j]>>i&1)^1];
		  ans+=1ll*k*(1ull<<i);
		}
	}
	printf("%lld
",ans);
  return 0;
}