自动搬运

查看原文

来自洛谷，原作者为

	XZhuRen 骄子风采，青春闪耀

搬运于2025-08-24 22:55:10，当前版本为作者最后更新于2025-07-12 17:25:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对操作扫描线，执行序列分块，则额外维护一个分块进行加操作。

序列分块部分，每个块内维护珂朵莉树，则会进行 $\mathcal{O}(q\sqrt{n}+(n+q))$ 次覆盖操作，其中前面的 $\mathcal{O}(\sqrt{n})$ 次通过块上打标记实现，则 odt 实际参与的覆盖次数是线性级别。

对询问扫描线设当前扫描到 $R$，则维护 $[L,R]$ 的序列值是简易的，然而我们不可以在每个询问处都处理出来。

考虑一次 $2$ 操作的贡献：

对于散块的处理是简易的，利用常数-根号次修改的分块对时间轴维护即可，接下来考虑整块：

有 $\mathcal{O}(\sqrt{n})$ 次整块。

若整块打了标记 $(col,t)$，则现在相当于贡献到时间 $[1,col]$ 整块和，其他部分为 $0$，则在同一个分块上更新即可。

反之，整块为珂朵莉树形式，这里对于不同时间有不同的贡献，暴力操作会有 $\mathcal{O}(n)$ 的复杂度，不可以直接维护。

首先每个块维护一个时间轴的分块代表起始时间在 $L$ 的答案。

假设一个块没有修改，则在不改变的时候维护一个标记 $cnt$，代表整个块被询问了多少次。则我们每次询问就直接查询 $L$ 处的答案即可，乘上 $cnt$ 即可，这一部分要 $\mathcal{O}(1)$。

带上修改（即 $\mathcal{O}(n+m)$ 次散块变化），则在保留 $cnt$ 的情况下，直接将新加的贡献 $(col,t)$ 算入，同时在本块维护的分块上减去被覆盖的 $(col,t)$ 的 $cnt$ 次贡献。

核心就是分块套珂朵莉树，这个 Trick 有另一道题：P7983。