Возвращение Злого Морти

Автор задачи: Даниил Орешников, разработчики: Даниил Орешников и Егор Юлин

Заметим следующий факт: если мы скажем, что отрезок $$$[a, b]$$$ «меньше» отрезка $$$[c, d]$$$ при $$$b < c$$$, то получится отношение частичного порядка, а ответом будет являться разбиение всех отрезков на минимальное количество возрастающих последовательностей. Это может быть подсказкой к решению: воспользуемся идеей из алгоритма поиска НВП за $$$\mathcal{O}(n \log n)$$$.

Но здесь, вместо поиска НВП, будем также обрабатывать отрезки по очереди слева направо, но поддерживать текущее «оптимальное» разбиение отрезков на группы. Под оптимальностью в данном случае будем понимать

Аккуратным рассмотрением двух вариантов разбиения на группы можно показать, что добавление нового отрезка в более «оптимальное» разбиение приводит к не менее оптимальному новому разбиению, значит поддержание такого разбиения приведет к ответу, соответствующему минимальному числу групп в разбиении.

Осталось только научиться поддерживать это оптимальное разбиение. Отсортируем все отрезки по их левой границе и будем поддерживать правые концы всех групп в дереве поиска. Тогда, чтобы добавить очередной отрезок $$$[l, r]$$$, достаточно

  1. найти максимальный конец группы $$$r_i$$$, который меньше $$$l$$$;
  2. добавить отрезок $$$[l, r]$$$ в эту группу;
  3. удалить из дерева поиска $$$r_i$$$ и добавить вместо него $$$r$$$.

Действительно, добавление одного отрезка приводит к изменению правого конца ровно одной группы (либо к добавлению новой группы, если все $$$r_i \ge l$$$). Чтобы добиться лексикографически минимальной последовательности правых концов, следует заменить максимальный возможный $$$r_i$$$. Таким образом, все решение работает за $$$\mathcal{O}(n \log n)$$$.