E2. 墨西哥比索（困难版本）详细题解

1. 问题回顾

与 E1 相同，但增加了 $q$ 次更新操作（$q \le 10^5$）。每次更新添加一个新的已知单元格（赋值）。需要输出初始状态和每次更新后的方案数。

核心挑战：动态维护图的一致性（所有环的异或和为 $0$）和连通分量数。

---

2. 关键观察

从 E1 我们知道：

• 美丽网格 ⇔ 存在 $X[1..n]$ 和 $Y[1..m]$ 使得 $A_{i,j} = X[i] \oplus Y[j]$
• 已知单元格对应二分图中的边 $(i, j+n)$，权值为 $v$
• 方案数 = $(2^{30})^{K-1}$，其中 $K$ 是连通分量数
• 如果存在环的异或和不为 $0$，则答案为 $0$

重要性质：边只会被添加，不会被删除。因此：

• 一旦出现矛盾（环的异或和不为 $0$），之后的所有状态答案都是 $0$
• 我们可以找到第一个导致矛盾的边

---

3. 解决方案一：二分 + DSU

3.1 找到第一个矛盾边

使用二分查找（或倍增）找到第一个使得图不一致的边：

• 检查前 $x$ 条边是否一致
• 如果一致，增加 $x$；否则减小 $x$

检查方法：用 DFS 验证所有环的异或和是否为 $0$

3.2 维护连通分量数

对于前 $firstzero$ 条边（无矛盾），用 DSU 维护连通分量数：

• 初始：$n+m$ 个节点，$K = n+m$
• 每添加一条边，如果连接不同连通分量，$K$ 减少 $1$
• 方案数 = $(2^{30})^{K-1}$

3.3 时间复杂度

• 二分查找：$O(\log Q \cdot (n+m+K))$
• DSU 操作：$O((n+m+Q) \alpha(n+m))$
• 总复杂度：$O((n+m+Q) \log Q)$

---

4. 解决方案二：在线 DSU（带异或维护）

4.1 数据结构设计

维护每个节点到根节点的异或值 p[u]，满足：

• 对于任意节点 $u$，p[u] 表示从 $u$ 到根节点的路径异或和
• 查询 $u$ 和 $v$ 之间的异或值：p[u] ^ p[v]

合并操作（小到大合并）：

• 添加边 $(u, v, w)$，设 $U = find(u)$，$V = find(v)$
• 如果 $U = V$：
  • 检查 (p[u] ^ p[v]) == w
  • 如果不相等，标记矛盾
• 否则：
  • 将较小的树接到较大的树上
  • 计算新边的权值：new_w = p[u] ^ p[v] ^ w
  • 更新被接树的根节点的 p 值

4.2 维护连通分量数

与普通 DSU 一样，每成功合并一次，连通分量数减 $1$

4.3 时间复杂度

• 每次操作 $O(\log n)$（树高对数）
• 总复杂度：$O((n+m+Q) \log (n+m))$

---

5. 算法步骤（基于二分 + DSU）

1. 读入初始边（k 条）和更新边（q 条）
2. 构建初始图（只包含初始边），用 DFS 检查一致性
3. 二分查找第一个导致矛盾的更新边位置 firstzero
   - 对于每个 mid，构建前 mid 条更新边的图
   - 用 DFS 检查所有环的异或和是否为 0
4. 用 DSU 维护连通分量数：
   - 初始状态：包含所有初始边
   - 对于 i = 0 到 q-1：
     - 输出当前方案数 = (2^30)^{K-1} mod MOD
     - 如果 i < firstzero，添加第 i 条更新边到 DSU
5. 输出最终状态

---

6. 代码实现要点

// 预计算 (2^30)^i mod MOD
precalc[0] = 1;
for (int i = 1; i < Mxn; i++) {
    precalc[i] = (precalc[i-1] << 30) % MOD;
}

// 检查前 x 条边是否一致
bool check(int x) {
    // 构建图：初始边 + 前 x 条更新边
    // DFS 检查所有环
    // 返回是否所有环的异或和为 0
}

// DSU 维护连通分量
struct DSU {
    vector<int> leader, sz;
    int components;
    
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        leader[y] = x;
        sz[x] += sz[y];
        components--;
    }
};

---

7. 示例验证

输入示例：

3
3 3 8 1
... (8 条初始边)
3 3 1
2 5 2 0
...
2 5 0 2
...

输出：

1        // 初始状态，只有 1 种方案
0        // 第一次更新后，矛盾，答案为 0
489373567 // 第二个测试用例
651321892 // ...
769740174
489373567

---

8. 时间复杂度

• 二分查找：$O(\log Q \cdot (n+m+K+Q))$
• DFS 检查：$O(n+m+K+Q)$
• DSU 操作：$O((n+m+Q) \alpha(n+m))$
• 总复杂度：$O((n+m+Q) \log Q)$，满足 $n,m,k,q \le 10^5$ 的约束

---

9. 总结

核心思想：

1. 美丽网格 ⇔ 存在 $X[i]$ 和 $Y[j]$ 使得 $A_{i,j} = X[i] \oplus Y[j]$
2. 转化为二分图上的环异或检查
3. 边只增不减 → 第一个矛盾点后的答案全为 $0$
4. 二分查找第一个矛盾点
5. DSU 维护连通分量数，计算方案数 $(2^{30})^{K-1}$