题解：Cheese 交易验证系统

算法标签

• 并查集（DSU）
• 带权并查集
• 模运算系统
• 位运算与对数处理
• 多约束条件验证

问题分析

题目要求验证一系列奶酪交易的合理性。核心是维护农民之间奶酪价格的相对差值关系，并检查新交易是否与已有关系矛盾。

关键观察

1. 每笔交易 (i, j, A, B) 隐含约束：农民 $j$ 的奶酪价格比农民 $i$ 的奶酪价格高 $A$ 个单位（模某个值）
2. 当 $B = -1$ 时，表示精确差值 $A$
3. 当 $B \neq -1$ 时，表示差值 $A$ 在模 $B$ 意义下成立，且剩余交易使用面值至少为 $B$ 的钞票

核心思路

1. 多模数并查集系统

代码维护了 17 个并查集：

• 前 16 个：模数为 $2^0, 2^1, \dots, 2^{15}$
• 第 17 个：模数为 $10^9+7$，用于精确约束

每个并查集维护农民之间的相对价格差值。

2. 交易验证逻辑

对于交易 (u, v, a, b)：

• 如果 $b = -1$：需要在所有模数系统中验证一致性
• 如果 $b \neq -1$：需要在模 $2^0, 2^1, \dots, 2^{\lg b}$ 的系统中验证一致性

3. 带权并查集操作

bool check(int u, int v, int w) {
    if (Find(u) != Find(v)) return true;
    return (val[u] + w) % mod == val[v];
}

检查是否满足：$price[v] - price[u] \equiv w \ (\text{mod } m)$

void merge(int u, int v, int w) {
    int fu = Find(u), fv = Find(v);
    if (fu != fv) {
        fa[fv] = fu;
        val[fv] = (val[u] + w - val[v] + mod) % mod;
    }
}

合并时维护差值关系：$price[fv] = price[fu] + (price[u] + w - price[v])$

算法步骤

初始化

for (int i = 0; i < 16; i++) 
    tr[i].Init(1 << i);
tr[16].Init(MOD);  // 用于精确约束

处理每笔交易

1. 确定验证范围：

   int Lg = ~b ? __lg(b) : 16;
   

   • $b = -1$：验证所有 17 个系统
   • $b \neq -1$：验证模 $2^0$ 到 $2^{\lg b}$ 的系统

2. 验证一致性：

   for (int j = 0; j <= Lg; j++)
       ok &= tr[j].check(u, v, a);
   

3. 更新系统：

   if (ok) {
       for (int j = 0; j <= Lg; j++)
           tr[j].merge(u, v, a);
   }
   

正确性分析

模数选择的意义

• $2^k$ 模数：对应钞票面值的约束，确保可以用 $2^k$ 的倍数平衡交易
• 大质数模数：提供精确的全局约束，防止模数过小导致的错误接受

验证逻辑

交易有效当且仅当在所有相关模数系统中：

• 如果 $u, v$ 已连通，现有差值必须等于 $a$（模 $m$）
• 如果 $u, v$ 未连通，可以安全合并

复杂度分析

• 初始化：$O(17 \times N)$
• 每笔交易：$O(17 \times \alpha(N))$，其中 $\alpha(N)$ 是并查集操作的反阿克曼函数
• 总复杂度：$O(M \cdot \alpha(N))$，满足 $N, M \leq 5\times 10^5$ 的要求

算法优势

1. 高效验证：利用并查集快速检查一致性
2. 多粒度约束：通过不同模数系统捕捉各种精度要求
3. 增量更新：只有验证通过的交易才会更新系统状态
4. 处理不确定性：巧妙处理了精确约束和模糊约束的情况

适用场景

这种多模数并查集方法适用于：

• 带模运算约束的连通性检查
• 增量式约束验证系统
• 需要多精度验证的相对关系维护

该算法通过巧妙的模数系统设计，成功解决了交易验证中的多精度约束问题。