CF1249D2 Too Many Segments (hard version)

简单难度与困难难度的唯一差别是 $n,k$ 的范围。 给予 $n$ 条线段，这些线段可以有重叠部分甚至完全重叠在一起。第 $i$ 条线段 $[l_i,r_i](l_i\le r_i)$ 覆盖了所有整数点 $j$ 满足 $l_i\le j\le r_i$。 如果一个整数点被**超过** $k$ 条线段覆盖，那么就称之为 bad point（下文以坏点代替）。 你的任务是去掉最少的线段使得没有坏点的存在。

输入第一行是两个正整数，$n$ 和 $k$ $(1\le k\le n\le 2\times 10^5)$。 然后有 $n$ 行，每行两个正整数，其中的第 $i$ 行表示第 $i$ 条线段的两个端点 $l_i$ 和 $r_i$ $(1\le l_i\le r_i\le 2\times 10^5)$。

输出的第一行为一个整数 $m$ $(0\le m\le n)$，表示最少去掉多少条线段可以不再存在坏点。 第二行输出 $m$ 个不同的正整数 $p_1,p_2,\cdots p_m$ $(1\le p_i\le n)$ 表示你移除了的线段的编号。如果有不止一个答案，可以输出任意一个满足条件的答案。