和Tree and Xor思路一样CF1055F Tree and XOR
直接找到第k大val，可以直接建出trie，然后按位贪心
考虑比val大的数的和
还是用b[i]维护可能和i贡献的trie的位置
当val这一位是0时候，v[i]就可以和ch[b[i]][v[i]>>d&1^1]进行贡献
一个点与一个子树进行贡献，不容易做。
不妨把v进行sort，子树就是区间了！
直接枚举每一位进行xor贡献
O(nlog^2n)
注意，
题目要求(a,b)不等于(b,a)方便起见，k*=2，最后ans/=2
可以最后再取mod
第k大的贡献不会算上，额外考虑，但是注意只是剩下一些个第k大元素。
#include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mk(a,b) make_pair(a,b) #define numb (ch^'0') #define pb push_back #define solid const auto & #define enter cout<<endl #define pii pair<int,int> using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void output(T x){if(x/10)output(x/10);putchar(x%10+'0');} template<class T>il void ot(T x){if(x<0) putchar('-'),x=-x;output(x);putchar(' ');} template<class T>il void prt(T a[],int st,int nd){for(reg i=st;i<=nd;++i) ot(a[i]);putchar(' ');} namespace Miracle{ const int N=50005; const int mod=1e9+7; int v[N],a[N],b[N]; int n; ll k,val; int ch[N*30+20][2],tot,l[N*30+20],r[N*30+20]; int rt; int sz[N*30+20]; int pre[N][30][2]; ll ans; void ins(int v,int id){ if(!rt) rt=++tot,l[rt]=1,r[rt]=n; int x=rt; ++sz[rt]; for(reg d=29;d>=0;--d){ int c=(v>>d)&1; if(!ch[x][c]) ch[x][c]=++tot,l[tot]=id; x=ch[x][c]; r[x]=id; ++sz[x]; } } void fin(){ for(reg i=1;i<=n;++i) b[i]=rt; for(reg d=29;d>=0;--d){ ll s=0,t=0; for(reg i=1;i<=n;++i){ s+=sz[ch[b[i]][(v[i]>>d&1)^1]]; } if(s<k) k-=s,t=0; else t=1,val|=(1<<d); for(reg i=1;i<=n;++i){ b[i]=ch[b[i]][(v[i]>>d&1)^t]; } } } ll con(int l,int r,ll v){ if(!l||!r) return 0; --l; // cout<<" con "<<l<<" "<<r<<" v "<<v<<endl; ll ret=0; for(reg d=29;d>=0;--d){ int c=v>>d&1; ret=ret+(ll)(pre[r][d][c^1]-pre[l][d][c^1])*(1LL<<d); } return ret; } void calc(){ for(reg i=1;i<=n;++i) b[i]=rt; for(reg d=29;d>=0;--d){ int t=val>>d&1; // cout<<" dd "<<d<<" tt "<<t<<endl; if(!t){ for(reg i=1;i<=n;++i){ int c=v[i]>>d&1; ans+=con(l[ch[b[i]][c^1]],r[ch[b[i]][c^1]],v[i]); } } for(reg i=1;i<=n;++i){ b[i]=ch[b[i]][(v[i]>>d&1)^t]; } } } int main(){ rd(n);rd(k); if(k==0){ puts("0");return 0; } k=k*2; for(reg i=1;i<=n;++i){ rd(v[i]);//++mp[v[i]]; } sort(v+1,v+n+1); for(reg i=1;i<=n;++i) ins(v[i],i); // cout<<" kk "<<k<<endl; fin(); ans+=k*val; for(reg i=1;i<=n;++i){ for(reg d=29;d>=0;--d){ pre[i][d][0]=pre[i-1][d][0]; pre[i][d][1]=pre[i-1][d][1]; pre[i][d][(v[i]>>d)&1]++; } } // cout<<" ans1 "<<ans<<endl; calc(); ans/=2; ot(ans%mod); return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* */