题目描述：
给定长度为n的数列X={x1,x2,...,xn}和长度为m的数列Y={y1,y2,...,ym}，令矩阵A中第i行第j列的值Aij=xi xor yj，每次询问给定矩形区域i∈[u,d],j∈[l,r]，找出第k大的Aij。
题解：
由于n小m大，面向m建可持久化trie树。
查询时查区间内所有数，判断这一位是1时的排名。
代码：
#include<queue> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 1050 #define M 300050 #define P 550 inline int rd() { int f=1,c=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){c=10*c+ch-‘0‘;ch=getchar();} return f*c; } int n,m,p,ax[N],rt[M],dep[N]; struct node { int x,d; node(){} node(int x,int d):x(x),d(d){} friend bool operator < (node a,node b) { return a.d<b.d; } }tp; struct Trie { int tot,siz[32*M],ch[32*M][2]; int insert(int now,int x) { int u,ret,f; u=ret=++tot,f=rt[now-1]; for(int i=30;i>=0;i--) { ch[u][0]=ch[f][0],ch[u][1]=ch[f][1],siz[u]=siz[f]+1; int c = (x>>i)&1; ch[u][c]=++tot; u=ch[u][c],f=ch[f][c]; } siz[u]++; return ret; } int lf[N],rg[N]; int query(int u,int d,int l,int r,int k) { for(int i=u;i<=d;i++)lf[i]=rt[l-1],rg[i]=rt[r]; int ans=0; for(int i=30;i>=0;i--) { int cnt = 0; for(int j=u;j<=d;j++) { int c = (ax[j]>>i)&1; cnt+=siz[ch[rg[j]][!c]]-siz[ch[lf[j]][!c]]; } if(cnt>=k) { ans|=(1<<i); for(int j=u;j<=d;j++) { int c = (ax[j]>>i)&1; rg[j]=ch[rg[j]][!c],lf[j]=ch[lf[j]][!c]; } }else { k-=cnt; for(int j=u;j<=d;j++) { int c = (ax[j]>>i)&1; rg[j]=ch[rg[j]][c],lf[j]=ch[lf[j]][c]; } } } return ans; } }tr; int main() { n=rd(),m=rd(); for(int i=1;i<=n;i++)ax[i]=rd(); for(int x,i=1;i<=m;i++) { x=rd(); rt[i]=tr.insert(i,x); } p=rd(); while(p--) { int u,d,l,r,k; u=rd(),d=rd(),l=rd(),r=rd(),k=rd(); printf("%d\n",tr.query(u,d,l,r,k)); } return 0; }
BZOJ4103 [Thu Summer Camp 2015]异或运算
原文：https://www.cnblogs.com/LiGuanlin1124/p/10046294.html