题解 P5795 【[THUSC2015]异或运算】

· · 题解

异或k大问题当然是一位一位算啦～枚举每一位，算可能的答案中这一位有多少0有多少1就好。

发现结果和行，列都有关，且n很小，可以考虑枚举行，计算这一行有多少满足要求的。

对Y建一棵可持久化Trie，询问的时候每一行维护一下走到了Trie的哪里，根据01数量决定走哪边就好了。

#include <bits/stdc++.h>

inline int rd() {
  int a = 1, b = 0; char c = getchar();
  while (!isdigit(c)) a = c == '-' ? 0 : 1, c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return a ? b : -b;
}

const int N = 3e5 + 233;

int n, m, X[N], Y[N], p, pt[N][2];
int ch[N * 35][2], sum[N * 35], tot, root[N];

inline int insert(int pre, int val) {
  int now = ++tot, ret = now;
  for (int i = 31; ~i; --i) {
    int t = (val >> i) & 1;
    ch[now][t ^ 1] = ch[pre][t ^ 1];
    pre = ch[pre][t];
    now = ch[now][t] = ++tot;
    sum[now] = sum[pre] + 1;
  }
  return ret;
}

inline int solve(int x1, int x2, int y1, int y2, int k) {
  k = (x2 - x1 + 1) * (y2 - y1 + 1) - k + 1;
  for (int i = x1; i <= x2; ++i) {
    pt[i][0] = root[y1 - 1];
    pt[i][1] = root[y2];
  }
  int ret = 0;
  for (int s = 31; ~s; --s) {
    int cnt = 0;
    for (int i = x1; i <= x2; ++i) {
      int t = (X[i] >> s) & 1;
      cnt += sum[ch[pt[i][1]][t]] - sum[ch[pt[i][0]][t]];
    }
    int nxt = k <= cnt ? 0 : 1;
    if (nxt) k -= cnt;
    ret = (ret << 1) | nxt;
    for (int i = x1; i <= x2; ++i) {
      int t = ((X[i] >> s) & 1) ^ nxt;
      pt[i][0] = ch[pt[i][0]][t];
      pt[i][1] = ch[pt[i][1]][t];
    }
  }
  return ret;
}

int main() {
  n = rd(), m = rd();
  for (int i = 1; i <= n; ++i)
    X[i] = rd();
  for (int i = 1; i <= m; ++i) {
    Y[i] = rd();
    root[i] = insert(root[i - 1], Y[i]);
  }
  p = rd();
  while (p--) {
    int x1 = rd(), x2 = rd(), y1 = rd(), y2 = rd(), k = rd();
    printf("%d\n", solve(x1, x2, y1, y2, k));
  }
  return 0;
}