CF241B Friends

异或粽子的加强版，时间复杂度是 \(O(n log^2 w)\) ，其中 \(w\) 是值域 \(2^{30}\) ，原来的是和 \(k\) 有关的，相当于是 CF241B 的代码通过不了异或粽子，异或粽子的代码通过不了 CF241B（雾

先考虑一个整体的思路，求前 \(k\) 大，先需要求第 \(k\) 大，第 \(k\) 大直接先二分，然后判断 \(mid\) 的排名，所以子问题是在字典树上判断两两异或值大于等于 \(mid\) 的个数

要求大于等于 \(mid\) ，也就是说二进制下存在一个位置它是 1 且 \(mid\) 是 0 ，它之前的都和 \(mid\) 一样，那直接枚举每个数，然后在字典树上跳，如果 \(mid\) 这位是 1 的话就直接跳，如果是 0 的话，就统计是 1 的答案，然后跳 0 ，统计一下，因为贡献会互相算一次，所以算了两次，要除一下

那么现在求完了第 \(k\) 大，我们要求前 \(k\) 大的 \(a_i\oplus a_j\) 和，直接枚举 \(a_i\) ，现在就是要求大于 \(kth\) ，如果这位 \(kth\) 是 1 就直接跳，如果是 0 就先统计再跳，跟之前差不多，但是统计的时候要统计这样一个东西：以 \(i\) 为根节点的子树内第 \(k\) 位为 1 的数的个数。再统计直接枚举位数就好了，如果这 \(a_i\) 这一位是1的话，要容斥一下，统计的话就是算贡献，乘 \(2^k\) ，很常见的算贡献方式。记得最后要除 2

但是要注意，如果有数和第 \(k\) 大相同就要减掉那些数

#include<bits/stdc++.h>
#define il inline 
#define maxn 50001
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll inv2=500000004ll;
il int read(){
	char c;int x=0,f=0;
	while(!isdigit(c=getchar()))f|=(c=='-');
	while(isdigit(c))x=(x*10)+(c^48),c=getchar();
	return f?-x:x;
}
int n,a[maxn],tot=0;
ll k,kth;
int trie[maxn*30][2],cnt[maxn*30];
int res[maxn*30][31]; // 以i为子树里，第k位是1的数的个数
il void insert(int id){
	int u=0;
	for(int i=30;i>=0;i--){
		int c=(a[id]>>i)&1;
		if(!trie[u][c])trie[u][c]=++tot;
		u=trie[u][c],cnt[u]++;
		for(int k=0;k<=30;k++) 
			if((a[id]>>k)&1)res[u][k]++;
	}
}
il ll check(ll x){
	ll tot=0;
	for(int i=1;i<=n;i++){
		int u=0;
		for(int j=30;j>=0;j--){	
			int c1=(a[i]>>j)&1,c2=(x>>j)&1;
			if(c2)u=trie[u][c1^1];
			else tot+=cnt[trie[u][c1^1]],u=trie[u][c1];
			if(!u)break;
		}
		tot+=cnt[u];
	}
	return tot/2;
}
ll ans=0;
il void calc(){
	for(int i=1;i<=n;i++){
		int u=0;
		for(int j=30;j>=0;j--){
			int c1=(a[i]>>j)&1,c2=(kth>>j)&1;
			if(c2)u=trie[u][c1^1];
			else{
				for(int k=0;k<=30;k++){
					int c3=(a[i]>>k)&1;
					if(c3)ans=(ans+(1ll<<k)*(cnt[trie[u][c1^1]]-res[trie[u][c1^1]][k])%mod)%mod;
					else ans=(ans+(1ll<<k)*res[trie[u][c1^1]][k]%mod)%mod;
				}
				u=trie[u][c1];
			}
			if(!u)break;
		}
		ans=(ans+cnt[u]*1ll*kth%mod)%mod;
	}
	ans=(ans*inv2)%mod,ans=((ans-(check(kth)-k)*kth%mod)%mod+mod)%mod;
}
int main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		insert(i);
	}
	ll lt=0,rt=(1ll<<30)+1;
	while(lt+1<rt){
		ll mid=(lt+rt)>>1;
		if(check(mid)>=k)lt=mid;
		else rt=mid;
	}
	kth=lt,calc();
	printf("%lld\n",ans);
	return 0;
}