P7603 [THUPC2021] 鬼街(减半警报器模板)

P7603 [THUPC2021] 鬼街（减半警报器模板）

还是，我太弱了；所以又是研究一晚上才写出来，所以还是吧我对这道题的理解讲讲。

这种题目一般是你需要维护一个数据结构，初始给定了一些范围，每个范围有权值。每次把包含一个点的所有范围都减去 \(x\。你需要维护每个范围被减到 \(<0\ 的最早时刻。

多个独立子区间构成就如图一，我们可以不重不漏的吧一个区间分成多个子区间。

由于线段的值是子区间的和，呢么一定有至少一个子区间是大于 \(\frac{Sum}{Size}\ 的，如果有一个子区间被将为 \(0\ 一下，我们就将线段重新平分。

读完题目会发现，这道题就符合了所说的“当每个检测的区间是由多个独立子区间构成，多个区间可能用到相同的子区间”。我们可以吧每个质因子作为一个子区间维护。

后对于增加报警器的操作，因为报警器只能检测安放后的次数，又为了不影响前面的子区间，我们考虑改变本段。考虑将本段的子段的累计先赋值成当前已经记录的数量，再把目标加上这个值，我们就优雅的记录了这个数。而在区间求和的时候就可以得到一种优雅的写法。

val[k] -= sum[k] - tmp[k] , tmp[k] = sum[k]

对于每一次闹鬼，就是把输入数的所有质因子（也就是一个子区间）减去上权值，如果这时此区间将为 \(0\ 及以下，则就可能得到答案，或者需要重新分配子区间的值。

赋值时有一个细节，我们可以直接赋值上取整。

若 \(x \mid k\，

根据鸽笼原理,最小的最大值为 \(\frac {sum} {k}\ 符合。

每个质因子权值最大为 \(\frac {sum} {k + 1}\，

另外不要忘了“真实的 \(y = y' \bigoplus LastAns\”。

本质和第一篇题解没有区别，但是传送门[Link]。