题解：P15094 [UOI 2025 II Stage] Three Queries

happybob · 2026-02-04 11:14:52 · 题解

思考一会 polylog 感觉不太可做，考虑根号做法。

有一些思路，一个是对操作一涉及到的位置个数根号分治，一个是对序列分块，还有一个是考虑到操作一本质在维护一个集合 S，支持加入删除，查询区间和 S 交的本质不同颜色数，所以考虑能不能操作分块。

根号分治不是很好做，由于有序列的单点修改所以每种颜色出现次数是会变化的，相对不容易处理。先考虑序列分块。

对于带修区间数颜色，经典做法是维护每个位置之前的最靠后的与其同色位置。对于 i 记其为 p_i，询问区间 [l,r] 即求 \sum \limits_{i=l}^r [p_i<l]。对于这个题，操作一维护了一个集合 S，支持向 S 内加入删除，查询的是 \sum \limits_{i=l}^r [p_i<l]\times [a_i \in S]。对序列单点修改只会影响 O(1) 个 p。

序列分块之后，将查询区间 [l,r] 拆为整块和散块，散块容易维护，整块则需要求这一块内所有颜色的 p 的最小值中有多少数比 l 小。对于一类修改，对于每一块相当于删除或插入一种颜色。有 O(n\sqrt n) 次单点修改和前缀求和，只能做到 O(n \sqrt n \log n)。

另一个思考角度是操作分块，看起来是有道理的。序列的单点修改是相对简单的，故考虑只对一类操作分块，也就是考虑本次询问和上个关键点的 S 的对称差，大小为 O(\sqrt n)，只需要对于其中每种颜色判定其目前是否在区间 [l,r] 中出现，以及当时是否在区间 [l,r] 中出现。现在问题变为每种颜色维护一个序列，支持总共 O(n) 次单点修改和 O(n\sqrt n) 次区间求和，这时就可以分块平衡了。由于不可能对每种颜色维护长度为 n 的序列，所以把这种颜色出现过的位置拉出来离散化后再分块就行。时间复杂度 O(n\sqrt n)，空间看起来不难做到线性。