BZOJ4103 异或运算

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

Sample Output

6
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 ;

 }