Классическая несложная задача, которая имеет много разных решений, но почему-то оценена как довольно сложная. Давайте читать условие:
Мы видим довольно большие входные данные: количество отрезков и точек до ста тысяч. То есть нельзя просто для каждой точки проверить все отрезки и посчитать. Даже если отсортировать отрезки по левому концу и считать только до того, который начинается правее заданной точки, тоже не подходит.
Можно использовать сжатие координат и потом с помощью дерева отрезков находить ответ, но это слишком сложно для такой задачи.
Классическим способом решения подобных задач является сканлайн (сканирующая прямая, метод заметающей прямой): необходимо сложить все события (начало отрезка, конец отрезка, координаты точек) в один вектор, отсортировать его и рассматривать элементы по порядку.
Например в нашей задаче можно для каждого события "начало отрезка" прибавлять единицы к некоторому счётчику, а для событий "конец отрезка" - вычитать единицу. Тогда в момент события "точка" в счётчике как раз будет ответ на задачу - количество открытых отрезков, которые ещё не закрылись.
Красота и простота этого решения ломается тем, что в один вектор надо сложить разнородные данные - отрезки и точки. Поэтому надо добавлять разные поля, помечающие, что это за событие.
Ещё одним подводным камнем является правильная сортировка событий, которые происходят в один момент времени. Так как нам важно, чтобы сначала произошли все открытия отрезков, затем обработались точки, а потом закрытия. И чем больше типов событий, тем хитрее будет компаратор для сортировки.
Поэтому предлагаю сделать небольшую модификацию решения:
в вектор с событиями складывать только начала отрезков и сами точки, а концы отрезков поддерживать в сете.
Это уменьшает количество типо событий и надо лишь следить, чтобы точки, соответствующие началам отрезков при сортировке оказались раньше, чем интересующие нас точки.
Данных довольно много, поэтому лучше писать на C++. Хоть на Python и можно сдать эту задачу, это сделал лишь один человек.
Подключим библиотеки. Нам понадобятся вектор, сет и алгоритм сортировки.
Создадим вектора для отрезков и для событий. Оба они будут содержать пары. Для отрезков, понятно, что это начало и конец отрезка. А в векторе событий будем хранить координату и номер отрезка или точки. Чтобы их отличать, номера отрезков будет хранить со знаком "-". Именно это и даст нам нужный порядок при сортировке событий в одной точке.
В 16-ой строке проверяем, чтобы первое число действительно было левым концом отрезка, потому что в условии задачи это не гарантируется. И, при необходимости, меняем концы местами. Если убрать эту проверку, то получите неверный ответ на 6 тест.
Теперь можно считать координаты точек. Отдельно их нигде хранить не надо, поэтому сразу будем записывать в вектор событий:
Благодаря хитрости с хранением данных, вектор событий теперь можно отсортировать без каких-либо компараторов:
Заведём сет для хранения правых концов отрезков и вектор для хранения ответов и пойдём по всем событиям по порядку:
Тогда возможны две ситуации:
- либо это начало некоторого отрезка (то есть второе значение в паре меньше нуля и по модулю равно номеру отрезка),
- либо это заданная точка (и второе значение в паре - это её номер).
В случае отрезка, мы просто добавляем его правый конец в сет, чтобы знать, что ещё один отрезок теперь открыт.
В случае точки, надо сначала выкинуть из сета все отрезки, которые уже закрыты (потому что у нас нет отдельного события на закрытие отрезка). И тогда все оставшиеся отрезки и будут теми, которым принадлежит точка:
И в ответ кладём их количество.
Вывод вектора с ответами:
Такой трюк можно распространить и на более сложные случаи. Например у каждого отрезка был бы вес и надо было находить суммарный вес, покрывающий точку. Тогда просто в сете тоже была пара чисел: координата правого конца и вес отрезка. А вот если бы надо было находить вес максимального отрезка, покрывающего точку, то это немного сложнее, предлагаю подумать и предложить решение в комментариях.
Предыдущий выпуск: Задача 229. Двухтуровая олимпиада
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
