Too Many Segments (hard version)

简单难度与困难难度的唯一差别是$n,k$的范围 给予$n$条线段，这些线段可以有重叠部分甚至完全重叠在一起。第$i$条线段$[l_i,r_i](l_i≤r_i)$覆盖了所有整数点$j$满足$l_i≤j≤r_i$ 如果一个整数点被**超过**$k$条线段覆盖，那么就称之为bad point（下文以坏点代替） 你的任务是去掉最少的线段使得没有坏点的存在 ### 输入格式 输入第一行是两个正整数，$n$和$k$$(1≤k≤n≤2*10^5)$ 然后有$n$行，每行两个正整数，其中的第$i$行表示第$i$条线段的两个端点$l_i$和$r_i$$(1≤l_i≤r_i≤2*10^5)$ ### 输出格式 输出的第一行为一个整数$m(0≤m≤n)$，表示最少去掉多少条线段可以不再存在坏点 第二行输出$m$个不同的正整数$p_1,p_2,…p_m(1≤p_i≤n)$表示你移除了的线段的编号。如果有不止一个答案，可以输出任意一个满足条件的答案。

The only difference between easy and hard versions is constraints. You are given $ n $ segments on the coordinate axis $ OX $ . Segments can intersect, lie inside each other and even coincide. The $ i $ -th segment is $ [l_i; r_i] $ ( $ l_i \le r_i $ ) and it covers all integer points $ j $ such that $ l_i \le j \le r_i $ . The integer point is called bad if it is covered by strictly more than $ k $ segments. Your task is to remove the minimum number of segments so that there are no bad points at all.

The first line of the input contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 2 \cdot 10^5 $ ) — the number of segments and the maximum number of segments by which each integer point can be covered. The next $ n $ lines contain segments. The $ i $ -th line contains two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le 2 \cdot 10^5 $ ) — the endpoints of the $ i $ -th segment.

In the first line print one integer $ m $ ( $ 0 \le m \le n $ ) — the minimum number of segments you need to remove so that there are no bad points. In the second line print $ m $ distinct integers $ p_1, p_2, \dots, p_m $ ( $ 1 \le p_i \le n $ ) — indices of segments you remove in any order. If there are multiple answers, you can print any of them.

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

3
4 6 7 

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

3
1 4 5 

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

4
1 3 5 6