Посчитайте количество вложенных друг в друга отрезков

На прямой даны N отрезков (в реальной жизни это могут быть промежутки времени, например), которые заданы координатами их левого и правого конца. Для каждого данного отрезка необходимо узнать, сколько из данных отрезков полностью находятся в нем. Один отрезок полностью содержится во втором, если левый конец первого отрезка находится правее левого конца второго отрезка, а правый конец первого находится левее правого конца второго. Предложите как можно более эффективный способ решения этой задачи. Гарантируется, что все концы данных отрезков различны.

Если вы придумали решение, то написать и проверить его вы можете здесь, на codeforces.

Решение за О(n²) (полный перебор)

Давайте для каждого отрезка из набора перебером найдем все отрезки, для которых выполняется условие «вложенности». Если да, то увеличим ответ для текущего рассматриваемого нами отрезка на единицу. Несложно понять, что данное решение работает за O(n²): для каждого из N отрезков мы перебираем N отрезков. Можно ли быстрее? Да!

Решение за О(n log n) (сортировка + структуры данных)

Отсортируем все отрезки по левому концу и будем рассматривать их в уже отсортированном порядке. Вспомним условие «вложенности»: левый конец первого отрезка правее левого конца второго отрезка, и правый конец первого отрезка левее правого конца второго отрезка. Несложно понять, что благодаря отсортированности все левые концы еще нерасмотренных отрезков будут правее левого конца рассматриваемого отрезка. Таким образом, все нерасмотренные отрезки потенциально являются вложенными в рассматриваемый: ведь для них уже выполняется одно из двух условий «вложенности» (про левые концы). Осталось узнать, сколько из них действительно являются таковыми — для этого нужно понять, сколько из нерассмотренных отрезков имеют правый конец левее правого конца рассматриваемого отрезка.

Для этого будем поддерживать структуру данных, которая может добавить и удалять из себя числа и отвечать на запросы вида: «сколько чисел во мне меньше X?», причем все операции должны выполняться за O(log n). Такой структурой данных может быть, например, декартово дерево, дерево Фенвика, дерево отрезков, или tree из ext/pb_ds/detail/standard_policies.hpp (если вы пишете на С++). Перед выполнением алгоритма для решения задачи сложим в нашу структуру координаты всех правых концов отрезков.

Теперь, чтобы узнать сколько из нерассмотренных отрезков имеют правый конец левее правого конца рассматриваемого отрезка, достаточно просто осуществить запрос к структуре данных «сколько чисел в тебе меньше, чем координата правого конца рассматриваемого отрезка». Ответ на этот запрос и будет ответом для рассматриваемого на данный момент нами отрезка. После запроса необходимо убрать координату правого конца отрезка из структуры данных, чтобы ответы для всех следующих отрезков были корректны: ведь левый конец рассматриваемого отрезка левее (благодаря отсортированности) левый концов всех еще нерасмотренных отрезков.

Докажем, что данное решение работает за О(n log n). Сортировка всех отрезков происходит за O(n log n), складывание всех правых концов отрезков в структуру данных за  O(n log n), на стадии вычисления ответов мы рассмотрим n отрезков, для каждого из которых осуществим два запроса, оба из которых выполнятся за О(log n). Таким образом, вычисляем все ответы мы за O(n log n) с препроцессингом за O(n log n), а значит, и асимптотика всего решения O(n log n).

Повышаем сложность

Сможете ли вы решить эффективно данную задачу в случае, если концы отрезков могут совпадать?

См. также

Больше сайтов с подобными задачами вы можете найти в нашей подборке.