给定 \(n\) 个整数 \(a_1,a_2...a_n\) ，求出所有子段异或和前 \(k\) 大的和 .

\(1\leq n\leq 5\cdot 10^5,0\leq k\leq \min(\frac{n(n-1)}{2},2\cdot 10^5),0\leq a_i\leq 2^{32}-1\)

前缀和数组为 \(b_0,b_1,b_2,\cdots b_n\) ，那么 \([l,r]\) 的字段异或和就是 \(b_r\oplus b_{l-1}\) . 就相当于两两的异或和 . 很像 \(\rm{cf241b\ friends}\) ，但是，那题 \(k\) 会达到 \(\frac{n(n-1)}{2}\) ，但是此题只会有 \(2\cdot 10^5\) ，但是 \(n\) 的大小却是 \(10\) 倍 .

所以考虑枚举出来前 \(k\) 个最大的，而不是二分，考虑用一个 \(\rm{set}\) 维护对于每个 \(i\) 没有被枚举到的最大的异或和 . 然后每次找到最大的，加入答案，然后用 \(\rm{01trie}\) 找到当前 \(i\) 下一个插入 .

但是这样就会导致一个问题，\((i,j)\) 和 \((j,i)\) 会被计算两次 . 冷静一下发现，只要把 \(k\) 的数量乘上 \(2\) 倍，这个问题就可以解决 ，前 \(k\) 大的以 \((i,j)\) 和 \((j,i)\) 的形式每个都被计算到了两次 .

需要注意的是要开 \(\rm{long\ long}\) .

时间复杂度 : \(O(k\log a)\)

空间复杂度 : \(O(n\log a)\)

code

#include<bits/stdc++.h>
using namespace std;
char in[100005];
int iiter=0,llen=0;
inline char get(){
	if(iiter==llen)llen=fread(in,1,100000,stdin),iiter=0;
	if(llen==0)return EOF;
	return in[iiter++];
}
inline long long rd(){
	char ch=get();while(ch<'0'||ch>'9')ch=get();
	long long res=0;while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=get();
	return res;
}
inline void pr(long long res){
	if(res==0){putchar('0');return;}
	static int out[20];int len=0;
	while(res)out[len++]=res%10,res/=10;
	for(int i=len-1;i>=0;i--)putchar(out[i]+'0');
}
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
const int N=5e5+10;
int cnt=1;
class node{public:int num,ch[2];}ts[N*32];
inline void init(){for(int i=0;i<N*32;i++)ts[i]=(node){0,-1};}
inline void ins(long long val){
	int x=1;
	for(int i=31;i>=0;i--){
		int id=val>>i&1;
		if(!ts[x].ch[id])ts[x].ch[id]=++cnt;
		x=ts[x].ch[id];
	}
	ts[x].num++;
}
inline void dfs(int x){
	if(ts[x].ch[0]){
		dfs(ts[x].ch[0]);
		ts[x].num+=ts[ts[x].ch[0]].num;
	}
	if(ts[x].ch[1]){
		dfs(ts[x].ch[1]);
		ts[x].num+=ts[ts[x].ch[1]].num;
	}
}
inline long long qry(long long val,int k){
	long long res=0;
	int x=1;
	for(int i=31;i>=0;i--){
		int id=val>>i&1;
		if(!id){
			if(ts[x].ch[1]&&ts[ts[x].ch[1]].num>=k)x=ts[x].ch[1],res|=1ll<<i;
			else k-=ts[ts[x].ch[1]].num,x=ts[x].ch[0];
		}else{
			if(ts[x].ch[0]&&ts[ts[x].ch[0]].num>=k)x=ts[x].ch[0],res|=1ll<<i;
			else k-=ts[ts[x].ch[0]].num,x=ts[x].ch[1];
		}
	}
	return res;
}
int n,k;
int a[N],pos[N];
set<pair<long long,int> >s;
long long ans=0;
int main(){
	n=rd();k=rd();k=k<<1;n++;
	for(int i=1;i<n;i++)a[i]=rd();
	for(int i=1;i<n;i++)a[i]^=a[i-1];
	for(int i=0;i<n;i++)ins(a[i]);
	dfs(1);
	for(int i=0;i<n;i++)s.insert(mp(-qry(a[i],++pos[i]),i));
	for(int i=0;i<k;i++){
		auto it=s.begin();
		int id=it->se;
		ans+=-it->fi;
		s.erase(s.begin());
		if(pos[id]+1<n)s.insert(mp(-qry(a[id],++pos[id]),id));
	}
	pr(ans/2);
	return 0;
}