F. MEX OR Mania 题解

难度：2700 | 标签：位运算、并查集(DSU)、小到大合并、离线处理、数据结构

题目大意

给定一个数组，定义好子数组满足：

$$\text{mex}(\text{子数组}) - \text{OR}(\text{子数组}) = 1 $$

每次操作对数组单点加法，要求每次操作后输出数组中最长好子数组的长度。

约束：$n,q \le 10^5$，单点加法操作，多组测试用例。

---

核心数学转化（解题关键）

原条件 $\boldsymbol{\text{mex} - \text{OR} = 1}$ 是解题的突破口，我们推导其等价条件： 设子数组的 $\text{mex} = m$，$\text{OR} = s$，则 $s = m-1$。

1. $\text{mex}=m$ → 子数组包含 $0,1,...,m-1$ 所有数，且没有 $m$；
2. $\text{OR}=m-1$ → 子数组中所有数都 $\le m-1$（OR 不会超过最大值）。

进一步推导： 满足条件的 $s=m-1$ 一定是 $2^k - 1$（二进制全1），因为只有全1的数才能作为 OR 值且包含 $0\sim s$ 所有数。

最终结论：

一个子数组是好子数组 $\iff$ 存在整数 $k$，满足：

1. 子数组中所有元素 $< 2^k$；
2. 子数组包含 $0,1,...,2^k-1$ 全部数字。

这是整个算法的核心！我们只需要对每个 $k$ 求解，再取最大值即可。

---

解题思路

1. 枚举 $k$：$2^{17} = 131072 > 10^5$，因此只需枚举 $k=0\sim17$ 共18个值；
2. 有效元素：对每个 $k$，仅保留值 $<2^k$ 的元素，这些元素构成连续段；
3. 并查集(DSU)：对每个 $k$，用 DSU 维护连续有效段，每个连通块维护内部数字集合；
4. 合法性判断：连通块包含 $0\sim2^k-1$ 所有数 → 该连通块长度为合法候选；
5. 离线处理：单点加法不可逆，正序读入所有操作 → 执行到最终状态 → 倒序撤销操作，记录答案；
6. 全局最大值：维护所有 $k$ 对应的最长合法长度，即为答案。

---

算法细节

1. 离线处理技巧

题目是单点加法，无法在线高效维护，因此采用离线倒序：

• 先读入所有 $q$ 次更新，直接执行到数组最终状态；
• 从最后一次更新倒序撤销操作，还原每一步的数组状态，记录答案；
• 最后正序输出答案。

2. 并查集优化

对每个 $k$ 独立维护 DSU：

• 合并相邻的有效元素（值 $<2^k$）；
• 用 small to large（小到大合并） 优化集合合并，保证复杂度；
• 每个连通块维护数字集合，判断是否包含 $0\sim2^k-1$。

3. 全局最大值维护

用 MaxSet 维护所有 $k$ 对应的最长合法长度，快速获取全局最大值。

---

代码模块详解

1. GoodSet（连通块数字管理器）

维护连通块内的数字，判断是否包含 $0\sim2^k-1$，返回合法长度：

struct GoodSet {
  map<int, int> mp;   // 统计数字出现次数
  int size;           // 连通块总长度
  int k;
  bool is_good() {    // 包含0~2^k-1所有数 → 合法
    return (int) mp.size() == (1 << k);
  }
  int get_value() {   // 合法返回长度，否则0
    return is_good() ? size : 0;
  }
};

2. MaxSet（全局最大值管理器）

维护所有合法长度，快速获取最大值：

struct MaxSet {
  map<int, int> mp;
  int get_max() { return mp.rbegin()->first; } // 取最大值
};

3. DSU（按k维护连通块）

对每个 $k$ 维护连续有效段，支持合并、更新元素：

struct DSU {
  vector<int> par;            // 并查集父节点
  vector<GoodSet> comp;       // 每个连通块的数字集合
  MaxSet good_lengths;        // 连通块合法长度
  void merge(int u, int v);   // 合并连通块（小到大优化）
  void update_in_component(int u, int x, bool insert); // 更新元素
};

4. 核心逻辑

• 初始化：执行所有更新到最终状态，初始化每个 $k$ 的 DSU；
• 倒序撤销：撤销更新，修改 DSU，记录答案；
• 输出答案。

---

完整AC代码

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 9, Q = 3e5 + 9;
using ll = long long;
 
// 维护连通块内的数字集合，判断是否合法
struct GoodSet {
  map<int, int> mp;
  int size;
  int k;
  GoodSet() {}
  GoodSet(int _k): k(_k), size(0) { };
  void insert(int x, int c = 1) {
    mp[x] += c;
    size += c;
  }
  void erase(int x) {
    if (mp[x] == 1) mp.erase(x);
    else mp[x]--;
    size -= 1;
  }
  void merge(GoodSet oth) {
    for (auto [x, c]: oth.mp) insert(x, c);
  }
  // 判断是否包含0~2^k-1所有数
  bool is_good() {
    return (int) mp.size() == (1 << k);
  }
  int get_value() {
    return is_good() ? size : 0;
  }
};
 
// 维护全局最大值
struct MaxSet {
  map<int, int> mp;
  void insert(int x) { mp[x]++; }
  void erase(int x) {
    mp[x]--;
    if (mp[x] == 0) mp.erase(x);
  }
  int get_max() { return mp.rbegin() -> first; }
};
 
// 每个k对应的并查集
struct DSU {
  int n, k;
  vector<int> par;
  vector<GoodSet> comp;
  MaxSet good_lengths;
  DSU() {}
  DSU(int _n, int _k): n(_n), k(_k) {
    par.resize(n + 1);
    comp.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      par[i] = i;
      comp[i] = GoodSet(k);
      good_lengths.insert(comp[i].get_value());
    }
  }
  int find(int u) {
    return par[u] = (par[u] == u ? u : find(par[u]));
  }
  // 小到大合并优化
  void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return;
    good_lengths.erase(comp[u].get_value());
    good_lengths.erase(comp[v].get_value());
 
    if (comp[u].mp.size() < comp[v].mp.size()) {
      swap(comp[u].mp, comp[v].mp);
      swap(comp[u].size, comp[v].size);
    }
    comp[u].merge(comp[v]);
    comp[v].mp.clear();
    good_lengths.insert(comp[u].get_value());
    par[v] = u;
  }
  // 更新连通块内的元素
  void update_in_component(int u, int x, bool insert = true) {
    u = find(u);
    good_lengths.erase(comp[u].get_value());
    insert ? comp[u].insert(x) : comp[u].erase(x);
    good_lengths.insert(comp[u].get_value());
  }
};

DSU f[18];        // 枚举k=0~17
ll a[N];          // 数组（开long long避免溢出）
int id[Q], x[Q], ans[Q];

void solve() {
  int n, q; cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i];
  // 离线：执行所有更新到最终状态
  for (int i = 1; i <= q; i++) {
    cin >> id[i] >> x[i];
    a[id[i]] += x[i];
  }

  MaxSet se;
  // 初始化每个k的并查集
  for (int k = 0; (1 << k) <= n; k++) {
    f[k] = DSU(n, k);
    for (int i = 1; i <= n; i++) {
      if (a[i] < (1 << k)) f[k].update_in_component(i, a[i], true);
    }
    // 合并相邻有效元素
    for (int i = 2; i <= n; i++) {
      if (a[i] < (1 << k) && a[i-1] < (1 << k)) f[k].merge(i-1, i);
    }
    se.insert(f[k].good_lengths.get_max());
  }

  // 倒序撤销更新，记录答案
  for (int qid = q; qid >= 1; qid--) {
    ans[qid] = se.get_max();
    int i = id[qid], sub = x[qid];
    for (int k = 0; (1 << k) <= n; k++) {
      se.erase(f[k].good_lengths.get_max());
      // 移除旧值，加入新值（撤销加法）
      if (a[i] < (1 << k)) f[k].update_in_component(i, a[i], false);
      if (a[i] - sub < (1 << k)) f[k].update_in_component(i, a[i] - sub, true);
      // 若元素变为有效，合并相邻段
      if (a[i] >= (1 << k) && a[i] - sub < (1 << k)) {
        if (i > 1 && a[i-1] < (1 << k)) f[k].merge(i-1, i);
        if (i+1 <= n && a[i+1] < (1 << k)) f[k].merge(i, i+1);
      }
      se.insert(f[k].good_lengths.get_max());
    }
    a[i] -= sub;
  }
  // 输出答案
  for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
 
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) solve();
  return 0;
}

---

复杂度分析

1. 枚举 $k$：共 $18$ 个，常数级；
2. 并查集合并：小到大合并，总复杂度 $\mathcal{O}(n \log n)$；
3. 总复杂度：$\mathcal{O}(18 \cdot n \log n)$，完全适配 $n,q \le 10^5$ 的限制；
4. 空间复杂度：$\mathcal{O}(n \log n)$，满足内存限制。

---

关键技巧总结

1. 数学转化：将复杂的 mex-OR=1 转化为包含完整数字集合的简单条件；
2. 离线处理：解决单点加法无法在线维护的问题；
3. 小到大合并：优化并查集的集合合并效率；
4. 多维度DSU：对每个 $k$ 独立维护，枚举所有可能的合法情况。