题面：给定长度为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<=1000,m<=300000）
思路：因为n比较小，所以维护第二维，然后暴力询问第一维。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010,maxm=300010,maxt=10000010;
int n,m,x[maxn],y[maxm],q,a,b,c,d,k;
struct Tree{
struct node{int size,son[2];}t[maxt];
int tot,root[maxm],a[maxm],t1[maxn],t2[maxn];
int newnode(){return ++tot;}
void insert(int id,int val){
root[id]=newnode();t[root[id]].size=t[root[id-1]].size+1;
int now=root[id],pre=root[id-1];
for (int j=31,v;j>=0;j--){
v=(val>>j)&1;t[now].son[v]=newnode();
t[t[now].son[v]].size=t[t[pre].son[v]].size+1;
t[now].son[v^1]=t[pre].son[v^1];
now=t[now].son[v],pre=t[pre].son[v];
}
}
void query(int u,int d,int l,int r,int rank){
for (int i=u;i<=d;i++) t1[i]=root[l-1],t2[i]=root[r];
int res=0;
for (int k=31;k>=0;k--){
int sum=0;
for (int i=u;i<=d;i++){
int v=(x[i]>>k)&1;
sum+=t[t[t2[i]].son[v^1]].size-t[t[t1[i]].son[v^1]].size;
}
if (rank<=sum){
for (int i=u;i<=d;i++){
int v=(x[i]>>k)&1;
t1[i]=t[t1[i]].son[v^1],t2[i]=t[t2[i]].son[v^1];
}
res|=(1<<k);
}
else{
for (int i=u;i<=d;i++){
int v=(x[i]>>k)&1;
t1[i]=t[t1[i]].son[v],t2[i]=t[t2[i]].son[v];
}
rank-=sum;
}
}
printf("%d
",res);
}
}Trie;
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&x[i]);
for (int i=1;i<=m;i++) scanf("%d",&y[i]);
for (int i=1;i<=m;i++) Trie.insert(i,y[i]);
for (scanf("%d",&q);q;q--) scanf("%d%d%d%d%d",&a,&b,&c,&d,&k),Trie.query(a,b,c,d,k);
return 0;
}