题解：P11872 异或盒子 1

algo_h · 2025-03-09 19:01:39 · 题解

比赛结束后几秒钟调出来的，提交失败，写个题解纪念一下。

考虑每次“加一”操作对每个二进制位的影响（代码中的 \mathrm{changes} 变量）。对每个数预处理出每个二进制位首次变化需要的“加一”次数并加入 \mathrm{changes} 中（代码中的 \mathrm{add\_num} 函数）后，该数第 i 位再次变化还需要的“加一”次数就恒为 2^i 了（代码中的 \mathrm{update\_changes} 函数）。

在此基础上，可以动态维护 \mathrm{changes}，当需要改变一个数的时候，可以利用异或操作的幂等性，实现为在 \mathrm{changes} 中同时加入原来的数和新的数的贡献（代码中 \mathrm{main} 函数里的两次 \mathrm{add\_num} 操作）；当需要执行“加一”操作时，利用 \mathrm{changes} 中的信息直接更新答案即可。

时空复杂度 O(n\log n)（空间复杂度可以压缩到线性），目前最优解。

#include <array>
#include <iostream>
#include <vector>

#define endl '\n'

using namespace std;

int n, q;
vector<int> v;
vector<array<int, 20>> changes;

void add_num(int u, int o = 0)
{
  for(int i = 0; i < 20; ++i) {
    int j = o + (-u & ((1 << i) - 1));
    if(j > q) break;
    ++changes[j][i];  // 自然溢出
  }
}

void update_changes(int i)
{
  for(int j = 0; j < 20; ++j) {
    if(i - (1 << j) >= 0) changes[i][j] += changes[i - (1 << j)][j];  // 自然溢出
  }
}

int main()
{
  int ans = 0;
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  v.resize(n);
  changes.assign(q + 1, { 0 });
  for(int &u : v) cin >> u, add_num(u), ans ^= u;

  int s = 0;
  for(int i = 0; i < q; ++i) {
    int o, x, y;
    cin >> o;
    if(o == 0) {
      cin >> x >> y, --x;
      add_num(v[x] + s, s);
      ans ^= v[x] + s;
      v[x] = y - s;
      ans ^= v[x] + s;
      add_num(v[x] + s, s);
    } else if(o == 1) {
      update_changes(++s);
      for(int j = 0; j < 20; ++j) ans ^= (changes[s][j] & 1) << j;
    } else {
      cout << ans << endl;
    }
  }
  return 0;
}