Codeforces Round 975 (Div. 1) |
---|
Закончено |
Это сложная версия задачи. В этой версии ограничения на $$$n$$$ и ограничение по времени выше. Вы можете совершать взломы только в том случае, если решены обе версии задачи.
Назовём множество (замкнутых) отрезков сложным, если оно может быть разбито на некоторые подмножества так, что
Вам даны $$$n$$$ отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$$$. Найдите максимальный размер сложного подмножества этих отрезков.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество отрезков.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$l_1, l_2, \ldots, l_n$$$ ($$$1 \le l_i \le 2n$$$) — левые концы отрезков.
Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$r_1, r_2, \ldots, r_n$$$ ($$$l_i \leq r_i \le 2n$$$) — правые концы отрезков.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число: максимальный размер сложного подмножества заданных отрезков.
331 2 35 4 651 2 3 6 85 4 7 9 1053 1 4 1 57 2 6 5 10
3 4 4
В первом наборе входных данных все пары отрезков пересекаются, поэтому оптимально сформировать одну группу, содержащую все три отрезка.
Во втором наборе входных данных не существует подходящего разбиения для всех пяти отрезков. Корректное разбиение с четырьмя отрезками выглядит следующим образом: $$$\{\{ [1, 5], [2, 4] \}, \{ [6, 9], [8, 10] \}\}$$$.
В третьем наборе входных данных оптимально составить одну группу, содержащую все отрезки, кроме второго.
Название |
---|