二进制警报器
在线解决以下问题:
给定长度为 \(n\) 的数组,\(q\) 次操作:
单点加(或多点加,视为多次单点加)
设置警报器 \((S,v)\),当集合 \(S\) 对应位置的和达到 \(v\) 时报警。
为了区分,我们将原问题中的报警称为终止报警。
我们希望得到一个 \(O(1)-O(|S|\log{V})\) 的做法(即对于一次单点加 \(O(1)\) 维护,对于一个警报器均摊 \(O(|S|\log{V})\) 维护)。
这就是本文所描述的二进制警报器算法。
二进制警报器的结构如下:
我们为每个警报器维护一个阈值 \(h\)。对于报警器集合 \(S\) 中一个位置的单点加,若这次操作跨过(对于一次单点加操作 \(x \mapsto x+v\),其跨过的点集为 \((x,x+v]\))了 \(2^h\) 的倍数,报警器就产生一次过程报警。
初始时,我们将 \(h\) 设为 \(\log{V}\)。
对于一个警报器 \((S,v,h)\),其阈值 \(h\) 需要满足在发生终止报警前至少发生一次过程报警。
换言之,如果假设 \(x\) 之后第一个 \(2^h\) 的倍数为 \(nx_{x,h}\),\(h\) 应当满足:\(v-\sum_{x \in S}a_x > \sum_{x \in S} (nx_{a_x,h}-1-a_x)\)。如果不满足这一条件,我们需要将 \(h\) 减小。
(或者更简洁,\(v > \sum_{x \in S} (nx_{a_x,h}-1)\))
比较显然的一点:\(\sum_{x \in S} (nx_{a_x,h}-a_x-1)\) 是 \(O(|S|2^h)\) 级别的。
以上的报警器结构相当于这样一个过程:
-
接受一个新的变化
-
如果变化满足阈值条件,发出过程警报
-
如果发出过程警报,检查是否需要发出终止警报。
显然我们只需要考察两个指标来衡量算法复杂度:报警次数和维护时间。
先考虑其报警次数。
对于一个阈值 \(h_0\) 来说,其报警次数是 \(O(|S|)\) 的。
这是由于当阈值 \(h=h_0\) 时,\(v-\sum a_i\) 是 \(O(|S|2^{h_0})\) 级别的,否则 \(h\) 会更大。
一个元素两次触发过程警报代表 \(\sum a_i\) 增长了至少 \(2^{h}\),经过 \(O(|S|)\) 次报警后 \(v-\sum a_i\) 至少减少了 \(O(|S|2^h)\)。
于是,一个警报器的报警总次数应当是 \(O(|S|\log{V})\) 的。总报警次数就是 \(O(q|S|\log{V})\),可以接受。
然后考虑如何维护警报器结构。
事实上,由于报警器的报警次数是合理的,我们只需要完成两个工作:
- 快速找到需要报警的警报器
首先对于每个 \((位置,h)\) 存下所有的警报器编号(vector
或链表什么的)。
对于一次单点加 \(x \mapsto x+v\),我们可以通过二进制优化 \(O(1)\) 得出会报警的所有 \(h\)。
具体来说,我们只需要知道报警的最大 \(h\) 即可。因为 \(2^{h-\Delta}|2^{h}\)。
就是 \(x \oplus (x+v)\) 的最高位。
//前面已经做了 a[x]+=vl
//st[x] 表示 x 的警报器的 h 集合
ull Set=((2ull<<(W-__builtin_clzll(a[x]^(a[x]-vl))))-1)&st[x]
\(W\) 是范围,ll/ull
就是 63
。
- 快速修正警报器阈值(重构警报器)。
首先一个警报器重构次数是 \(\log{V}\) 次的,所以重构时可以 \(O(|S|)\),但是判断重构要做到 \(O(1)\)。
判断重构可以维护一个值 \(r=\sum_{x \in S} (nx_{a_x,h}-1)\),对这个值的维护是 \(O(1)\) 的。因为我们也可以通过二进制优化 \(O(1)\) 得出 \(nx\),这本质上就是要将低位清空并进位:
ull nx(ull x,int h){return x+(1ull<<h)-(x&((1ull<<h)-1));
}
然后如果 \(v \leq r\) 就要重构。每次 \(h\) 减一后暴力重新维护 \(r\) 即可。
于是我们就完成了二进制警报器的维护。
做到了对于原序列 \(O(1)\) 维护,对于警报器均摊 \(O(|S|\log{V})\) 维护。
更详细的示例代码实现会放在第一道例题里。
例题
LOJ#6764. 「THUPC 2021」鬼街
警报器问题的直接应用一例。
有集合加,设置警报器两种操作,二进制警报器可以做到 \(O(|S|)-O(|S|\log{V})\)。本题集合大小是 \(O(\omega(n))\) 的。
通过线性筛预处理最小质因数,可以快速求出 \(n\) 的所有质因数集合。
于是整个问题就是 \(O(n+q\omega(n)\log{V})\),\(n\) 是线性筛。
Code。
(其实我一开始死活过不去,重构+换写法后莫名其妙就过了,原来的。我的理解是可能是重更新之类的啥影响了结果)
upd:这个好像写假了,比其他实现几乎慢了一倍,因为忘加判断导致无需重构的报警器也会重新 \(O(|s|)\) 扫描加入 vector
。这是修正后的代码:Code。
2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite B.Call Me Call Me
链接。
你要邀请 \(n\) 个人来参加会议。第 \(i\) 个人会同意参加当且仅当区间 \([l_i,r_i]\) 内已经有 \(k_i\) 个人同意参加。问最多能邀请多少个人来参加。
(直接复制了 Tutorial 的题意)
也是警报器问题,需要在区间和达到 \(k\) 时报警。
显然要先划分为相对固定的几个区间。
Idea 1:线段树
通过线段树,我们可以将区间划分为 \(O(\log{N})\) 个固定区间。也就是警报器集合 \(|S|\) 是 \(O(\log{N})\) 的。
于是就是设置报警器,报警后 \(O(\log{n})\) 次单点加,反复运行。设置警报器和修改都是 \(O(N)\) 次的,通过二进制警报器容易做到 \(O(n\log^{2}{n})\)。
Idea 2:多叉树
我们试图继续优化这个做法。
由于二进制警报器 \(O(1)-O(|S|\log{V})\) 的特征,我们修改需要 \(O(\log{N})\),但是警报器侧复杂度是 \(O(\log^2{N})\)。
我们希望平衡这两个复杂度。
考虑将二叉树改成 \(B\) 叉树,另外对于每个节点维护 \(O(B^2)\) 个儿子区间的和。
那么一次点修会影响到 \(O(B^2\log_{B}{N})\) 个信息。
一个区间可以拆成 \(O(\log_{B}{N})\) 个信息(本来 \(B\) 叉树期望是 \(O(B\log_{B}{N})\) 的信息量,但是维护了儿子区间信息,中间的 \(B\) 个信息变成了一个)。
于是修改 \(O(B^2\log_{B}{N})\),查询 \(O(\log_{B}{N}\log{N})\),平衡得到 \(B^2\log_{B}{N}=\log_{B}{N}\log{N} \Rightarrow B=\sqrt{\log{N}}\),得到 \(O(N\log{N}\log_{\sqrt{\log{N}}}{N})=O(\frac{N\log^2{N}}{\log{\log{N}}})\)。
算了一下 \(O(\log{\log{N}})\) 才 \(2\) 左右……。
我还是写二叉吧。
8169ms 838936kb。
另外,我还写了链表版本,可以发现时空均有显著优化。
6956ms 355428kb。
多叉树版本:被鸽子捞走了。
2019 Summer Petrozavodsk Camp, Day 2: 300iq Contest 2 (XX Open Cup, Grand Prix of Kazan) F. Fast Spanning Tree
QOJ
有 \(m\) 个元组 \((a_i, b_i, s_i)\),其中 \(1 \leq a_i, b_i \leq n,a_i \neq b_i\),且 \(s_i\) 是一个非负整数。
之后,他开始执行以下过程:
如果不存在这样的 \(i\),使得 \(a_i\) 和 \(b_i\) 位于图的不同连通分量中,并且 \((a_i 所在连通分量的顶点总权重) + (b_i 所在连通分量的顶点总权重) \geq s_i\),则结束该过程。
否则,选择满足条件的最小 \(i\),在 \(a_i\) 和 \(b_i\) 之间添加一条边,将 \(i\) 输出,并重复该过程(但此时是在更大的图上)。
就是要动态维护出现的连通块的信息,并且在指定连通块和达到指标时报警。
考虑一个启发式合并的技巧,这样点-连通块关系只会转移总共 \(O(n\log{n})\) 次。
合并时我们可以暴力修改受影响的警报器的监控集合(本题的集合大小是 \(O(1)\) 的),然后利用链表高速合并的性质快速维护 \((位置,h)\) 的那个信息。
本题 \(V=O(n)\)。一次连边转移 \((位置,h)\) 是 \(O(\log{n})\) 的,共 \(O(n\log{n})\)。一个警报器集合至多修改 \(O(\log{n})\) 次,共 \(O(m\log{n})\)。剩下部分就是二进制警报器的正常分析:合并时产生的点加 \(O(1)\),警报器维护 \(O(\log{n})\),故共 \(O((n+m)\log{n})\)。
代码下午写。