← 返回题目列表

Codeforces · 1764/H

H. 多米的油漆 2

中文机器翻译题面 查看原题

Doremy 有 $$$n$$$ 桶油漆,由长度为 $$$n$$$ 的数组 $$$a$$$ 表示。桶$$$i$$$包含颜色为$$$a_i$$$的油漆。最初,$$$a_i=i$$$。

Doremy 有 $$$m$$$ 段 $$$[l_i,r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$)。每个段描述一个操作。操作$$$i$$$执行如下:

- 对于每个$$$j$$$,使得$$$l_i < j \leq r_i$$$,设置$$$a_j := a_{l_i}$$$。

Doremy 还选择了一个整数 $$$k$$$。她想知道从 $$$0$$$ 到 $$$m-1$$$ 的每个整数 $$$x$$$ 执行操作 $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$ 后数组中不同颜色的数量。你能帮她计算这些值吗?请注意,对于每个 $$$x$$$ ,我们从初始数组开始,并按给定的顺序仅执行给定的 $$$k$$$ 操作。

输入

输入的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1\le n,m\le 2\cdot 10^5$$$, $$$1 \le k \le m$$$) - 数组 $$$a$$$ 的长度、操作总数以及 Doremy 选择的整数。

以下 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$l_i$$$、$$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$) — 第 $$$i$$$ 段的边界。

输出

输出 $$$m$$$ 个整数。如果我们从初始数组开始并执行操作 $$$x \bmod m +1, (x+1) \bmod m + 1, \ldots, (x+k-1) \bmod m +1$$$ 操作,那么第 $$$(x+1)$$$ 个整数应该是数组中不同颜色的数量。

示例

输入 #1

7 5 5
3 5
2 3
4 6
5 7
1 2

输出 #1

3 3 3 3 2

输入 #2

10 9 4
1 1
2 3
3 4
7 9
6 8
5 7
2 4
9 10
1 3

输出 #2

6 6 7 6 5 5 7 7 7

注意

在第一个测试用例中,下图分别显示了 $$$x=0,1,2$$$ 值的结果数组。