二进制报警器

· · 算法·理论

题目描述

有 n 个变量 x_1, x_2, \dots, x_n，一开始都是 0。现在要处理两种操作：

对于每个 \mathtt{watch} 操作，我们要找出是哪个 \mathtt{add} 操作让它响的。

假设每个集合 S 的大小都不超过 K，而且 K 比较小。

如果可以离线做，用"整体二分"可以 O(K \times Q \times \log Q) 解决。

解法

方法一：减半报警器

先介绍一个简单点的办法：减半报警器。

对于每个 \mathtt{watch}(\{s_1, s_2, \dots, s_k\}, \mathtt{th})，我们把它拆成 k 个小报警器：

\mathtt{watch}\left(\{s_i\}, \left\lfloor\frac{\mathtt{th}}{k}\right\rfloor\right)

如果这些小报警器都没响，那原来的报警器肯定也不会响。所以原来的报警器最多响 O(\log_{\frac{k}{k - 1}} \mathtt{th}) 次。

怎么实现： 每个变量都开个优先队列，存着跟它有关的所有小报警器。每次有报警器响的时候：

  1. 算一下真正的阈值是多少（因为可能有些变量加上去了但没让报警器响，阈值就不准了）。
  2. 再把新的小报警器加回去。

每次报警器响要 O(K \log Q) 时间。

假设 V 是所有阈值里面最大的那个，总时间是：

K\, \log Q \, \frac{\log V}{\log K - \log (K - 1)} < K^2 \, \log Q \log V

（因为 \log(k) - \log(k - 1) > \frac{1}{k}）

方法二：二进制报警器

二进制报警器用两个技巧让速度更快。

基本想法

对于每个 \mathtt{watch}(\{s_1, s_2, \dots, s_k\}, \mathtt{th})，我们找最大的 t 使得 2^t \leq \left\lfloor\frac{\mathtt{th}}{k} \right\rfloor。换句话说，t 是最大的数使得 \left\lfloor \frac{\mathtt{th}}{2^t} \right\rfloor \geq k。

然后我们加 k 个小报警器：

\mathtt{watch'}\left(\{s_i\}, 2^t\right)

区别在于： \mathtt{watch'} 在变量和跨过 2^t 的倍数时就响，而不是增加 2^t 才响。比如，变量和从 7 变成 9，那么 \mathtt{watch'}(4) 会响，因为跨过了 8（8 是 4 的倍数）。

- **不会漏掉：** 如果 $\mathtt{watch}\left(\left\lfloor\frac{\mathtt{th}}{k}\right\rfloor\right)$ 响了，那么 $\mathtt{watch'}(2^t)$ 肯定也响了。这样就不会漏掉真正的报警。 - **不会响太多：** 如果 $\mathtt{watch'}(2^t)$ 响了 3 次，那么 $\mathtt{watch}\left(\left\lfloor\frac{\mathtt{th}}{k}\right\rfloor\right)$ 至少响了 1 次。因为前面说过 $\mathtt{watch}$ 最多响 $O(K \log V)$ 次，所以 $\mathtt{watch'}$ 也不会响太多次。 #### 优化 1：不用优先队列 用 $\mathtt{watch'}$ 的话，就不用优先队列了（省掉 $O(\log Q)$），因为只有 $O(\log V)$ 种不同的小报警器。 **有点慢但没关系：** $\mathtt{add}$ 操作从 $O(\log Q)$（用优先队列）变成 $O(\log V)$（遍历所有种类的小报警器），但总时间不变。 #### 优化 2：不用重算阈值 在减半报警器里，每次报警器响都要重新算阈值。但用二进制报警器时，如果当前的阈值 $\mathtt{th'}$ 满足 $\left\lfloor \frac{\mathtt{th'}}{2^t} \right\rfloor \geq k$，就不用算了。 因为如果有些变量加上去但没让报警器响，这些增量加起来最多是 $(k - 1) \times 2^t$，这种情况下原来的报警器肯定不会响。只有当 $t$ 变小的时候才需要重新算，这样又省了 $O(K)$ 时间。 #### 最终时间 把这些优化都用上，总时间是 $O(K \log Q \log V)$。