题解：CF1764H Doremy's Paint 2

masterhuang · 2025-06-28 23:15:15 · 题解

给定一个长度为 n 的序列 a_{1},a_2,\cdots,a_n，初始 a_i = i。

有 m 个操作，第 i 个操作有参数 l_i, r_i，执行该操作会把 a_{l_i+1}\sim a_{r_i} 赋值为 a_{l_i}。

给定 k，对于所有 x = 1 \sim m，求依次执行 [x,x + k - 1] 中的操作后序列不同元素个数。

其中操作编号超过了 m 就对 m​ 取模。

1\le n,m\le 2\times 10^5,1\le k\le m

• 应该绝对没有 ^*3400，按照 rating 一年贬值 200 理论，应该是 ^*2800，差不多吧。

破环成链是显然的。这题依然不是维护值而是维护时刻。

我们从后往前扫，维护每个元素 i 贡献彻底被消除的时刻 f_i。

具体的，从后往前到 t 时刻，操作 [l,r]，会依次进行如下变化：

答案就是倒着做到 x 后，n-\sum [f_i\le x+k-1]​。

怎么维护呢？发现扫的过程中 f 的值域连续段个数不多啊。

你一次只会增加 O(1) 个连续段，于是连续段总数是 \mathcal{O}(n) 的。

珂朵莉树维护即可，[f_i\le x+k-1] 树状数组维护，复杂度 \mathcal{O}(n\log n)。

\bf{record}