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.

简单版本与困难版本的唯一区别在于约束条件。

你在坐标轴 $OX$ 上给定了 $n$ 条线段。这些线段可以相交、互相包含，甚至完全重合。第 $i$ 条线段为 $[l_i; r_i]$（其中 $l_i \le r_i$），它覆盖所有满足 $l_i \le j \le r_i$ 的整数点 $j$。

若一个整数点被严格多于 $k$ 条线段所覆盖，则称该点为坏点。

你的任务是移除最少数量的线段，使得最终不存在任何坏点。

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.

输入的第一行包含两个整数 $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$ 条线段的两个端点。

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.

第一行输出一个整数 $m$（$0 \le m \le n$）—— 使得不存在坏点所需移除的线段的最少数量。

第二行输出 $m$ 个互不相同的整数 $p_1, p_2, \dots, p_m$（$1 \le p_i \le n$）—— 以任意顺序输出你所移除的线段的下标。若存在多个答案，输出任意一个即可。