CF1249D2 Too Many Segments (hard version)

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.