第二分块 笔记

• CF896E Welcome home, Chtholly。
• P4117 [Ynoi2018] 五彩斑斓的世界。

考虑对序列分块，显然没有好的序列算法能够使整块在短的时间内完成操作，因此考虑从值域上寻找突破，设块内最大值是 $\mathrm{mx}$。

• 当 $2x>\mathrm{mx}$ 时，需要被操作的值域不超过一半，因此直接对 $(x,\mathrm{mx}]$ 进行操作。
• 当 $2x\le \mathrm{mx}$ 时，需要被操作的值域远超过不需要被操作的值域，所以直接对 $[0,x]$ 的数全部 $+x$，然后这个块打上一个 $-x$ 的 tag。

我们需要知道每个值域内的数具体是哪些位置的，因此涉及到多个数的合并，可以使用并查集，值域不断减小，不存在重复遍历，因此对于每个块时间复杂度是 $O(V\alpha )$。

至此已经可以通过 A，但是在 B 会空间不够，由于各个块之间没有什么关联，因此可以离线每个块单独做，把空间省下来。