题解：P10148 [Ynoi1999] M47升级型“钢铁阿诺”

XZhuRen · 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。