← 返回题目列表

Codeforces · 1249/D2

D2. 段太多(硬版)

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

简单版本和困难版本之间的唯一区别是限制。

您将在坐标轴 $$$OX$$$ 上获得 $$$n$$$ 段。线段可以相交、位于彼此内部甚至重合。第$$$i$$$段是$$$[l_i; r_i]$$$ ($$$l_i \le r_i$$$) 并且它覆盖了所有整数点$$$j$$$,使得$$$l_i \le j \le r_i$$$。

如果整数点被严格超过 $$$k$$$ 段覆盖,则该整数点被称为坏点。

您的任务是删除最少数量的段,以便根本没有坏点。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — 段数以及每个整数点可以覆盖的最大段数。

接下来的 $$$n$$$ 行包含段。第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$) — 第 $$$i$$$ 段的端点。

输出

在第一行中打印一个整数 $$$m$$$ ($$$0 \le m \le n$$$) — 您需要删除的最小段数,这样就不会出现坏点。

在第二行中打印 $$$m$$$ 不同的整数 $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le n$$$) — 以任意顺序删除的段的索引。如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9

输出 #1

3
4 6 7

输入 #2

5 1
29 30
30 30
29 29
28 30
30 30

输出 #2

3
1 4 5

输入 #3

6 1
2 3
3 3
2 3
2 2
2 3
2 3

输出 #3

4
1 3 5 6