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.

N/A

N/A