Лекция на тему "Сканирующая прямая"

• Сканирующая прямая или сканлайн - это метод для решения задач.  

• Метод позволяет сортировать запросы по определенному элементу.  

• Запросы разбиваются на ивенты, события, которые происходят последовательно.  

• Рассматривается задача нахождения точки, покрытой наибольшим количеством отрезков.  

• Точка с максимальным значением покрытости обязательно является концом отрезка.  

• Решение задачи включает перебор всех точек и проверку принадлежности к отрезкам.  

• Отрезки разбиваются на события двух типов: начало и конец.  

• События сортируются по координате x.  

• Начинающиеся отрезки покрывают дополнительные точки, заканчивающиеся - завершают текущие.  

• Заводится структура для хранения событий с полями x и type.  

• События сортируются с помощью компаратора.  

• Важно обрабатывать события в правильном порядке: сначала открывающиеся, затем закрывающиеся.  

• Заводится переменная для подсчета количества отрезков, покрывающих текущую точку.  

• При добавлении нового отрезка количество увеличивается, при завершении - уменьшается.  

• Обновляется максимальное количество отрезков, покрывающих текущую точку.  

• Решение задачи занимает O n log n времени.  

• Переходим к следующей задаче, решаемой похожим способом.  

• Нужно посчитать длину объединения отрезков.  

• Используем ивенты для обработки левой и правой границ.  

• Поддерживаем предыдущий икс и обновляем ответ при каждом ивенте.  

• Считаем, сколько отрезков покрывают каждую точку.  

• Используем сканирующую прямую для решения.  

• Сортируем отрезки и добавляем ивенты для точек.  

• Считаем количество пересекающихся отрезков для каждого отрезка.  

• Инвертируем задачу: количество пересечений равно n минус один минус количество непересечений.  

• Считаем количество непересекающихся отрезков и выводим результат.  

• Считаем длину объединения прямоугольников на плоскости.  

• Используем дерево отрезков для поддержания текущего состояния.  

• Обновляем ответ при каждом событии, умножая сумму на разницу иксов.  

• Дерево отрезков хранит пары чисел, где первое число отвечает за сумму всех единичек, а второе - за текущий элемент.  

• Вершины дерева отвечают за единственный элемент, и если сумма больше нуля, то первое число равно единице, иначе - нулю.  

• Для объединения пар чисел нужно сложить соответствующие значения в каждой паре.  

• Для подсчета суммы в дереве отрезков нужно сложить значения в корневой вершине.  

• Важно учитывать, что ответ содержится в левой части дерева.  

• Прибавление и вычитание единичек требует дополнительных действий, но общая идея решения понятна.  

• Для больших массивов можно использовать неявное дерево отрезков, где новые вершины создаются только при необходимости.  

• Неявное дерево отрезков позволяет хранить массив на 10^9 элементов.  

• Решение с неявным деревом отрезков имеет сложность O n log log y.  

• Задача: поддерживать количество различных чисел на отрезке.  

• Запросы сортируются по правой границе, и для каждого запроса поддерживается количество различных чисел.  

• Вводится массив кт, который равен нулю или единице в зависимости от текущего элемента и его положения в последовательности.  

• Все запросы сортируются по правой границе.  

• Если отрезок содержит равные значения, берется сумма.  

• Решение задачи включает обработку новых чисел и новых правых границ.  

• События делятся на новые числа и новые правые границы.  

• Хранится левая граница и индекс отрезка.  

• Сначала обрабатываются новые числа, затем пересчитывается ответ.  

• Если событие равно единице, обновляется значение кнт.  

• Если кнт равно нулю, значение кнт обновляется до айди.  

• Берется сумма элементов на отрезке и выводится в порядке айди.  

• Дерево отрезков используется для апдейта элементов и взятия суммы.  

• Можно использовать другие структуры данных, такие как дерево Фенвика.  

• Дерево отрезков проще в реализации и подходит для таких задач.  

• Метод сканирующий прямой используется для задач с заранее известными запросами.  

• Если запросы известны заранее, можно написать онлайн-решение.  

• Вопросы по задаче и лекции можно задать в конце.  

• Вопросы по лекции и задачам можно задать в конце.  

• Запись лекции будет выложена утром.  

• Прощание с аудиторией.