题目大意:
给定长度为n的数列X={x1,x2,...,xn}和长度为m的数列Y={y1,y2,...,ym},令矩阵A中第i行第j列的值(A_{ij} = x_i ext{ xor } y_j)每次询问给定矩形区域(i in [u,d],j in [l,r])找出第k大的(A_{ij}).
题解:
中午会宿舍的时候看了一眼题面hhhhhhhh.
瞄了一眼300000的数据范围就走了hhhhhhhh.
一中午想了快1h就是没做出来hhhhhhhhh.
直到下午来了机房看到了n<=1000 hhhhhh.
维护n颗可持久化01Trie暴力查询即可
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 1024;
const int maxm = 300010;
struct Node{
Node *ch[2];
int siz;
}*null,*root[maxm];
Node mem[maxm*40],*it;
inline void init(){
it = mem;null = it++;
null->ch[0] = null->ch[1] = null;
null->siz = 0;root[0] = null;
}
inline Node* insert(Node *rt,int x,int d){
Node *p = it++;*p = *rt;p->siz ++ ;
if(d == -1) return p;
int id = (x >> d)&1;
p->ch[id] = insert(p->ch[id],x,d-1);
return p;
}
int cnt;
Node *lnw[maxn],*rnw[maxn];int val[maxn];
int kth(int k,int d){
if(d == -1) return 0;
int tmp = 0;
for(int i=1,id;i<=cnt;++i){
id = (val[i] >> d) & 1;
tmp += rnw[i]->ch[id^1]->siz - lnw[i]->ch[id^1]->siz;
}
if(k <= tmp){
for(int i=1,id;i<=cnt;++i){
id = (val[i] >> d) & 1;
lnw[i] = lnw[i]->ch[id^1];
rnw[i] = rnw[i]->ch[id^1];
}return (1<<d) | kth(k,d-1);
}else{
for(int i=1,id;i<=cnt;++i){
id = (val[i] >> d) & 1;
lnw[i] = lnw[i]->ch[id];
rnw[i] = rnw[i]->ch[id];
}return kth(k - tmp,d-1);
}
}
int a[maxn],b[maxm];
int main(){
init();
int n,m;read(n);read(m);
for(int i=1;i<=n;++i) read(a[i]);
for(int i=1;i<=m;++i){
read(b[i]);
root[i] = insert(root[i-1],b[i],30);
}
int q;read(q);
while(q--){
int u,d,l,r,k;read(u);read(d);
read(l);read(r);read(k);
cnt = 0;
for(int i=u;i<=d;++i){
lnw[++cnt] = root[l-1];
rnw[cnt] = root[r];
val[cnt] = a[i];
}
printf("%d
",kth(k,30));
}
getchar();getchar();
return 0;
}