「权力药水」题解

核心算法与公式

1. 问题形式化

设：

• $H[i]$：第 $i$ 个萨满的高度
• $F_u(t)$：在第 $t$ 天时萨满 $u$ 信任的萨满集合
• 查询：$\min\{|H[x] - H[y]| : x \in F_X(V), y \in F_Y(V)\}$

2. 位集表示

设总边数为 $E$，用位集 $\text{BS}_u(t)$ 表示 $u$ 在第 $t$ 天的信任关系：

$$\text{BS}_u(t)[i] = \begin{cases} 1 & \text{如果存在边 } (u, \text{id}[i]) \text{ 且该边在第 } t \text{ 天有效} \\ 0 & \text{否则} \end{cases} $$

其中 $\text{id}[i]$ 是按高度排序后第 $i$ 个萨满的原始编号。

3. 分块递推公式

设块大小为 $B$，对于 $k = 0, 1, 2, \ldots, \lfloor m/B \rfloor$：

$$\text{Rec}[k] = \text{BS}(k \cdot B)$$

其中 $\text{BS}(t)$ 表示第 $t$ 天所有萨满的信任关系位集。

对于 $t \in [k \cdot B + 1, (k+1) \cdot B]$：

$$\text{BS}(t) = \text{Rec}[k] \oplus \bigoplus_{i=k \cdot B + 1}^{t} \Delta_i $$

其中 $\Delta_i$ 是第 $i$ 天边变化的位集差异：

$$\Delta_i = \text{flip}(p_i.\text{fi}) \oplus \text{flip}(p_i.\text{se}) $$

4. 查询处理算法

对于查询 $(X, Y, V)$：

1. 计算块索引：$k = \lfloor V / B \rfloor$
2. 恢复状态：$\text{BS} = \text{Rec}[k] \oplus \bigoplus_{i=k \cdot B + 1}^{V} \Delta_i$
3. 获取高度集合：$$A = \{H[\text{id}[j]] : \text{BS}_X[j] = 1\}$$ $$B = \{H[\text{id}[j]] : \text{BS}_Y[j] = 1\}$$
4. 排序：$A' = \text{sort}(A)$, $B' = \text{sort}(B)$
5. 双指针求最小值：$$\text{ans} = \min_{\substack{0 \le i < |A'| \\ -1 \le j < |B'|}} \begin{cases} A'[i] - B'[j] & \text{if } j \ge 0 \\ B'[j+1] - A'[i] & \text{if } j+1 < |B'| \end{cases} $$

5. 位集操作公式

翻转操作：

$$\text{flip}(x) : a[x \gg 6] \leftarrow a[x \gg 6] \oplus (1 \ll (x \& 63)) $$

下一个设置位：

$$\text{next}(p) = \begin{cases} x \ll 6 \mid \text{ctz}(a[x] \gg (y+1) \ll (y+1)) & \text{if } y < 63 \land (a[x] \gg (y+1)) \neq 0 \\ i \ll 6 \mid \text{ctz}(a[i]) & \text{对于 } i > x \text{ 且 } a[i] \neq 0 \\ \infty & \text{否则} \end{cases} $$

其中 $x = p \gg 6$, $y = p \& 63$，$\text{ctz}$ 计算尾部零的个数。

6. 时间复杂度分析

• 预处理：$O\left(m \cdot \frac{E}{64} \cdot \frac{1}{B}\right)$

• 每个查询：$O\left(B + D \log D + D\right)$

  • $B$：应用剩余变化
  • $D \log D$：排序信任的萨满高度
  • $D$：双指针扫描

• 总复杂度：$O\left(m \cdot \frac{E}{64} \cdot \frac{1}{B} + Q \cdot (B + D \log D)\right)$

7. 最优块大小

通过平衡预处理和查询时间，最优块大小为：

$$B_{\text{opt}} = \Theta\left(\sqrt{\frac{m \cdot E}{64 \cdot Q}}\right) $$

在实际实现中取 $B = 400$ 能在时间和空间之间取得良好平衡。

8. 空间复杂度

• 位集存储：$O\left(\frac{E}{64} \cdot \frac{m}{B}\right)$
• 其他数组：$O(n + m)$
• 总空间：$O\left(\frac{mE}{64B} + n + m\right)$