CF2170F Build XOR on a Segment 题解

蒟蒻君HJT · 2025-11-30 12:38:30 · 题解

可能第一个想法会是从不同的起点开始 dp，求出 f[x][y] 表示从某个起点开始，到右端点 x 为止，如果要异或出来 y，则至少需要选取几个整数。这个 dp 的转移是很简单的，但是询问个数太多了，即使对序列分块，只取每块的左端点作为起点，询问的复杂度也会爆炸。

那么观察一下，根据线性代数的知识，可以发现每个询问的答案不会超过 12，因为任意 13 个在 [0, 4095] 中的整数，一定存在 1 个整数能被其他 12 个整数的某个子集的异或表示，于是就可以去掉这个整数。然后就可以想到，从左往右 dp，假设当前右端点为 r，实时维护 f[x][y] 表示如果能使用的整数右边到 r 为止，且希望通过 y 个整数的异或凑出 x，则左端点的最大值是多少。即 [f[x][y], r] 中存在 y 个整数能异或得出 x。这样的话离线查询就很简单了，可以在扫描到右端点 r 时处理右端点为 r 的所有询问，找到最小的 y 使得 f[x][y]\geq l 即为答案。转移也是简单的，每次遍历整个 f 数组，然后 \max(f_{\text{old}}[x][y], f_{\text{new}}[x \ \text{xor}\ a[r]][y + 1])\to f_{\text{new}}[x \ \text{xor}\ a[r]][y + 1]。

算一下更新 f 的复杂度 O(n\times \max{a_i}\times \log \max{a_i})，大概是 5\times 10^8，常数很小，一看时间限制 5s，直接冲就完事了。

这场考虑到 dirty 程度 D>>>EF，不好评价。

#include <bits/stdc++.h>

typedef std::pair<int, int> pii;
int a[10005], n, q, f[4096][13], nf[4096][13], ans[1000005], val[1000005];
std::vector<pii> query[10005];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  scanf("%d", &q);
  for (int i = 1; i <= q; ++i) {
    int l, r;
    scanf("%d%d%d", &l, &r, &val[i]);
    query[r].push_back(pii(l, i));
  }
  memset(f, -1, sizeof(f));
  for (int i = 1; i <= n; ++i) {
    memcpy(nf, f, sizeof(f));
    for (int o = 0; o < 4096; ++o) {
      nf[a[i]][1] = i;
      for (int p = 1; p <= 11; ++p) {
        if (f[o][p] == -1) {
          continue;
        }
        nf[o ^ a[i]][p + 1] = std::max(nf[o ^ a[i]][p + 1], f[o][p]);
      }
    }
    memcpy(f, nf, sizeof(f));
    for (auto [x, y]: query[i]) {
      ans[y] = 0;
      for (int p = 1; p <= 12; ++p) {
        if (f[val[y]][p] >= x) {
          ans[y] = p;
          break;
        }
      }
    }
  }
  for (int i = 1; i <= q; ++i) {
    printf("%d ", ans[i]);
  }
  printf("\n");
  return 0;
}