[trick] 减半警报器

• 适用题目 \(\rightarrow\) 高速判断是否合法，但是不知道什么时候应该判断

• 核心思想 \(\rightarrow\) 鸽巢原理

每个警报所监视的所有集合 \(S\) 的 \(sum\) 要达到 \(d\) ，说明集合内至少有个元素的值大于等于 \(\frac{d}{|S|}\)，那我们把 \(\frac{d}{|S|}\) 作为警报数值，放在集合内所有元素维护的数据结构里，每次达到了这个阈值就拿出来 \(check\) 一下。

\(check\) 后要做的事：

首先删除当前警报器维护的所有集合中的当前警报器的阈值（懒标记删除）

接着 \(\rightarrow\)

• 若合法，记录答案
• 否则 \(d' = d - 当前警报器监视集合sum\)，然后将 \(\frac{d}{|S|}\) 作为警报阈值，丢入集合元素的数据结构中

鬼街