4103: [Thu Summer Camp 2015]异或运算
Time Limit: 20 Sec Memory Limit: 512 MB
Description
给定长度为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。
Input
第一行包含两个正整数n,m，分别表示两个数列的长度
第二行包含n个非负整数xi
第三行包含m个非负整数yj
第四行包含一个正整数p，表示询问次数
随后p行，每行均包含5个正整数，用来描述一次询问，每行包含五个正整数u,d,l,r,k，含义如题意所述。
Output
共p行，每行包含一个非负整数，表示此次询问的答案。
Sample Input
3 3
1 2 4
7 6 5
3
1 2 1 2 2
1 2 1 3 4
2 3 2 3 4
1 2 4
7 6 5
3
1 2 1 2 2
1 2 1 3 4
2 3 2 3 4
Sample Output
6
5
1
5
1
HINT
对于100%的数据，0<=Xi,Yj<2^31,
1<=u<=d<=n<=1000,
1<=l<=r<=m<=300000,
1<=k<=(d-u+1)*(r-l+1),
1<=p<=500
对n暴力，m建可持久化Trie
BZOJ+1，您的最佳选择
#include<bits/stdc++.h>
using namespace std;
template <class _T> inline void read(_T &_x) {
int _t; bool flag = false;
while ((_t = getchar()) != '-' && (_t < '' || _t > '')) ;
if (_t == '-') _t = getchar(), flag = true; _x = _t - '';
while ((_t = getchar()) >= '' && _t <= '') _x = _x * + _t - '';
if (flag) _x = -_x;
}
typedef long long LL;
const int maxn = ;
const int maxm = ;
const int DEP = ;
struct Trie {
int v, ch[];
}t[maxm * ];
int n, m, p, cnt;
int root[maxm], X[maxn], Y[maxm];
int Query(int u, int d, int l, int r, int K) {
static int lr[maxn], rr[maxn];
for (int i = u; i <= d; ++i)
lr[i] = root[l - ], rr[i] = root[r];
int res = , tot;
for (int i = DEP; i >= ; --i) {
tot = ;
for (int j = u, x; j <= d; ++j) {
x = ((X[j] >> i) & ) ^ ;
tot += t[t[rr[j]].ch[x]].v - t[t[lr[j]].ch[x]].v;
}
if (tot >= K) {
for (int j = u, x; j <= d; ++j) {
x = ((X[j] >> i) & ) ^ ;
rr[j] = t[rr[j]].ch[x];
lr[j] = t[lr[j]].ch[x];
}
res += << i;
} else {
for (int j = u, x; j <= d; ++j) {
x = ((X[j] >> i) & );
rr[j] = t[rr[j]].ch[x];
lr[j] = t[lr[j]].ch[x];
}
K -= tot;
}
}
return res;
}
void update(int r1, int &r2, int v, int dep) {
t[r2 = ++cnt] = t[r1], ++t[r2].v;
if (dep < ) return ;
update(t[r1].ch[(v >> dep) & ], t[r2].ch[(v >> dep) & ], v, dep - );
}
int main() {
//freopen("4103.in", "r", stdin);
//freopen("4103.out", "w", stdout);
read(n), read(m);
for (int i = ; i <= n; ++i) read(X[i]);
for (int i = ; i <= m; ++i)
read(Y[i]), update(root[i - ], root[i], Y[i], DEP);
read(p);
for (int i = , u, d, l, r, k; i <= p; ++i) {
read(u), read(d), read(l), read(r), read(k);
printf("%d\n", Query(u, d, l, r, k));
}
return ;
}