Too Many Segments (hard version)
Contest: Codeforces Round 595 (Div. 3)
Difficulty rating: 1800
Tags: data structures, greedy, sortings

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9

Example output:
3
4 6 7

Example input:
5 1
29 30
30 30
29 29
28 30
30 30

Example output:
3
1 4 5

Editorial:
In this problem, we need to implement the same greedy solution as in the easy version, but faster. Firstly, let's calculate for each point the number of segments covering it. We can do it using standard trick with prefix sums: increase $$$cnt_{l_i}$$$, decrease $$$cnt_{r_i + 1}$$$ and build prefix sums on the array $$$cnt$$$.
Let's maintain the set of segments that cover the current point, sorted by the right endpoint. We can do this with almost the same trick: append to the array $$$ev_{l_i}$$$ the index $$$i$$$ that says us that in the point $$$l_i$$$ the $$$i$$$-th segment is opened. And add to the $$$ev_{r_i + 1}$$$ the index $$$-i$$$ that says us that in the point $$$r_i + 1$$$ the $$$i$$$-th segment is closed. Note that you need to add $$$1$$$-indexed values $$$i$$$ because $$$+0$$$ and $$$-0$$$ are the same thing actually. We can change the array $$$cnt$$$ to carry the number of segments covering each point using some structure, but we don't need to do it. Let's maintain the variable $$$curSub$$$ that will say us the number of segments covering the current point that was already removed. Also, let's carry another one array $$$sub$$$ which will say us when we need to decrease the variable $$$curSub$$$.
So, we calculated the array of arrays $$$ev$$$, the array $$$cnt$$$ and we can solve the problem now. For the point $$$i$$$, let's remove and add all segments we need, using the array $$$ev_i$$$ and add $$$sub_i$$$ to $$$curSub$$$. Now we know that the set of segments is valid, $$$curSub$$$ is also valid and we can fix the current point if needed. While $$$cnt_i - curSub > k$$$, let's repeat the following sequence of operations: take the segment with the maximum right border $$$rmax$$$ from the set, remove it, increase $$$curSub$$$ by one and decrease $$$sub_{rmax + 1}$$$ by one.
Note that when we remove segments from the set at the beginning of the sequence of moves for the point $$$i$$$, we don't need to remove segments that we removed by fixing some previous points, and we need to pay attention to it.
Time complexity: $$$O(n \log n)$$$.