多区间第 k 大异或值(k较小)

链接：[P5283 十二省联考 2019] 异或粽子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：给定序列 a，求 $n^2$ 个子区间中前 k 大子区间异或和的和。

题解：首先区间异或和可以用前缀异或和 $O(1)$ 查询，那么题目转化为求前 k 大的点对异或的和。用堆来维护最大值，遍历序列求出所有固定右端点的第 1 大异或值，丢进堆里。每次取最大值，假设当前为 第5位的第 t 大值，则往堆内放入第 5 第 t+1 位最大值。注意同一个右端点加入次数有限制，比如第 1 位只有一个最大值。

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<queue>using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const int maxn=5e5+5;ll va[maxn<<6],kt[maxn],a[maxn],n,k,ans;
int p[maxn<<6][2],ct[maxn<<6],rt[maxn],now;
priority_queue<P,vector<P>,less<P> >pq;void insert(int u,int v,ll x)
{rt[v]=++now;int l=rt[u],r=rt[v];for(int i=32;i>=0;i--){int k=x>>i&1;p[r][k]=++now;p[r][k^1]=p[l][k^1];ct[r]=ct[l]+1;l=p[l][k],r=p[r][k];}va[r]=x; ct[r]=ct[l]+1;return;
}ll query(int u,ll x,int y)
{int r=rt[u];for(int i=32;i>=0;i--){int q=x>>i&1;if(ct[p[r][q^1]]>=y)r=p[r][q^1];else y-=ct[p[r][q^1]],r=p[r][q];}return va[r]^x;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>n>>k; insert(0,1,0);for(int i=2;i<=n+1;i++){cin>>a[i],a[i]^=a[i-1],insert(i-1,i,a[i]);}for(int i=2;i<=n+1;i++)pq.push(P(query(i-1,a[i],++kt[i]),i));while(k--){P x=pq.top(); pq.pop();ans+=x.first;if(kt[x.second]<x.second-1){pq.push(P(query(x.second-1,a[x.second],++kt[x.second]),x.second)); }}cout<<ans<<"\n";return 0;
}

多区间第 k 大异或值加强版

链接：CF241B Friends - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

与上面相比主要是 k 值扩大，无法枚举 k，采取二分的形式，先确定 k 值位置，然后将大于 k 值的和累加。每个点考虑层贡献。求取大于 k 值的所有数与一个数异或和的和可以先维护每个节点下边所有层带的 1 和 0 的个数，然后就可以直接遍历这个节点的 log 层考虑每层的贡献即可。复杂度 $O(nlo{g}^{2}w)$。

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>using namespace std;
typedef long long ll;
const int maxn=5e4+5;
const int mod=1e9+7;ll a[maxn],n,m,sum,res;
int p[maxn<<5][2],ct[maxn<<5],rt[maxn],l[maxn],r[maxn],now;
unsigned short int sm[maxn<<5][31][2];inline void insert(int u,int v,ll x)
{rt[v]=++now;int l=rt[u],r=rt[v];for(int i=30;i>=0;i--){int q=x>>i&1;p[r][q]=++now;ct[r]=ct[l]+1;p[r][q^1]=p[l][q^1];for(int j=i;j>=0;j--){sm[r][j][x>>j&1]=sm[l][j][x>>j&1]+1;sm[r][j][(x>>j&1)^1]=sm[l][j][(x>>j&1)^1];}l=p[l][q],r=p[r][q];}ct[r]=ct[l]+1;return;
}inline int query(int u,ll x,ll mid)
{int r=rt[u],cnt=0; for(int i=30;i>=0;i--){int q=x>>i&1;if(mid>>i&1)r=p[r][q^1];else{cnt+=ct[p[r][q^1]];r=p[r][q];}}cnt+=ct[r]; return cnt;
}inline bool check(ll mid)
{ll cnt=0;for(int i=2;i<=n;i++)cnt+=query(i-1,a[i],mid);return cnt>=m;
}void Query(int u,ll x,ll y)
{int r=rt[u],dep[31]={0};for(int i=30;i>=0;i--){int q=x>>i&1;if(y>>i&1)r=p[r][q^1];else{res+=ct[p[r][q^1]];for(int j=30;j>i;j--)dep[j]+=ct[p[r][q^1]]*(y>>j&1);dep[i]+=ct[p[r][q^1]];for(int j=i-1;j>=0;j--)dep[j]+=sm[p[r][q^1]][j][(x>>j&1)^1];r=p[r][q];}}res+=ct[r]; for(int i=30;i>=0;i--)dep[i]+=ct[r]*(y>>i&1);for(int i=30;i>=0;i--)sum+=dep[i]*(1ll<<i); return;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i],insert(i-1,i,a[i]);}ll l=0,r=1<<30;while(l<r){ll mid=l+r+1>>1;if(check(mid))l=mid;else r=mid-1;}for(int i=2;i<=n;i++)Query(i-1,a[i],l);cout<<((sum-(res-m)*l)%mod+mod)%mod<<"\n";return 0;
}

更优解法

因为二分出来的是一个数，所有点都跑这一个数，所以直接边把所有点的数往同一个方向移动即可。注意可持久化要左右都要继承或修改，不要忘了继承这一项。

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>using namespace std;
typedef long long ll;
const int maxn=5e4+5;
const int mod=1e9+7;ll a[maxn],n,k,cnt,ans,res;
int p[maxn<<5][2],ct[maxn<<5],rt[maxn],r[maxn],now;
short unsigned int sm[maxn<<5][31][2];inline void insert(int u,int v,int x)
{rt[v]=++now;int l=rt[u],r=rt[v];for(int i=30;i>=0;i--){int q=x>>i&1;p[r][q]=++now;ct[r]=ct[l]+1;for(int j=i;j>=0;j--){sm[r][j][x>>j&1]=sm[l][j][x>>j&1]+1;sm[r][j][(x>>j&1)^1]=sm[l][j][(x>>j&1)^1];}p[r][q^1]=p[l][q^1];l=p[l][q],r=p[r][q];}ct[r]=ct[l]+1;return; 
} inline void query()
{for(int i=2;i<=n;i++)r[i]=rt[i-1];ll dep[31]={0},y=0;for(int i=30;i>=0;i--){int cp=0;for(int j=2;j<=n;j++){cp+=ct[p[r[j]][(a[j]>>i&1)^1]];}if(cnt+cp>=k){for(int j=2;j<=n;j++){r[j]=p[r[j]][(a[j]>>i&1)^1];}y+=(1ll<<i);}else{cnt+=cp;for(int j=2;j<=n;j++){int nr=p[r[j]][(a[j]>>i&1)^1];for(int o=30;o>i;o--)dep[o]+=ct[nr]*(y>>o&1);dep[i]+=ct[nr];for(int o=i-1;o>=0;o--)dep[o]+=sm[nr][o][(a[j]>>o&1)^1];r[j]=p[r[j]][a[j]>>i&1];}}}for(int i=2;i<=n;i++){cnt+=ct[r[i]];for(int j=30;j>=0;j--){dep[j]+=ct[r[i]]*(y>>j&1);}}for(int i=30;i>=0;i--)ans+=(1ll<<i)*dep[i];res=y;return;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i],insert(i-1,i,a[i]);query();cout<<((ans-(cnt-k)*res)%mod+mod)%mod<<"\n";return 0;
}

多区间第 k 大异或值更优解法

链接：[P5795 THUSC2015]异或运算 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

上面通过枚二分来寻找第 k 大异或值。可以发现每次对 mid 都是使所有数异或出来为 mid，则可以直接将所有数进行同时转移，判定是该使其异或 $x_i$ 为哪一位去同时走。复杂度 $O(qnlogw)$。

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>using namespace std;
typedef long long ll;
const int maxn=3e5+5;int x[maxn],l[maxn],r[maxn],n,m,t;
int p[maxn<<5][2],ct[maxn<<5],rt[maxn],now;inline void insert(int u,int v,int x)
{rt[v]=++now;int l=rt[u],r=rt[v];for(int i=30;i>=0;i--){int q=x>>i&1;p[r][q]=++now;ct[r]=ct[l]+1;p[r][q^1]=p[l][q^1];l=p[l][q],r=p[r][q];}ct[r]=ct[l]+1;return;
}inline int query(int u,int v,int ql,int qr,int k)
{int ans=0;for(int i=ql;i<=qr;i++)l[i]=rt[u],r[i]=rt[v];for(int i=30;i>=0;i--){int res=0;for(int j=ql;j<=qr;j++){int q=x[j]>>i&1;res+=ct[p[r[j]][q^1]]-ct[p[l[j]][q^1]];}if(res>=k){ans+=1<<i;for(int j=ql;j<=qr;j++){int q=x[j]>>i&1;l[j]=p[l[j]][q^1],r[j]=p[r[j]][q^1];	}}else{k-=res;for(int j=ql;j<=qr;j++){int q=x[j]>>i&1;l[j]=p[l[j]][q],r[j]=p[r[j]][q];}} }return ans;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++)cin>>x[i];for(int i=1;i<=m;i++){int u; cin>>u,insert(i-1,i,u);}cin>>t;for(int i=1;i<=t;i++){int u,d,l,r,k;cin>>u>>d>>l>>r>>k;cout<<query(l-1,r,u,d,k)<<"\n";}return 0;
}