Дерево и сканирующая прямая

Дерево отрезков хранит одномерный массив. Сканирующая прямая делает задачу одномерной: одна координата становится временем, вторая — индексом в дереве.

Общая схема всегда одна:

1. превратить объекты в события на оси $x$;
2. отсортировать события;
3. идти слева направо, поддерживая деревом состояние по оси $y$;
4. в нужные моменты снимать с дерева ответ.

Подробнее про сам приём — раздел «Отрезки и сканирующая прямая»; здесь про то, что при этом делает дерево.

Порядок событий на равной координате

Самое частое место ошибки — не дерево, а сортировка. Если отрезок занимает $[l, r]$ включительно, то закрытие ставится в точку $r + 1$, и на одной координате закрытия обязаны обрабатываться раньше открытий.

Иначе отрезки $[1, 3]$ и $[4, 5]$, не пересекающиеся ни в одной точке, дадут в координате 4 пересечение: открытие второго успеет случиться до закрытия первого.

Проверка занимает минуту: возьмите ровно эти два отрезка и посчитайте максимальное покрытие. Должна выйти единица.

Площадь объединения прямоугольников

Классическая задача, в которой дерево хранит не сумму и не максимум, а минимум и количество минимумов.

Каждый прямоугольник даёт два события: в $x_1$ прибавить $+1$ на отрезке $[y_1, y_2)$, в $x_2$ прибавить $-1$. Между соседними событиями площадь растёт на

$$(x_{i+1} - x_i) \cdot (\text{длина покрытой части оси } y).$$

Покрытая часть — это вся длина минус длина участков с нулём. А нуль здесь всегда является минимумом, потому что счётчики неотрицательны. Отсюда трюк:

long long covered(int v, int tl, int tr) {
    if (minimum[v] > 0) return length(tl, tr);          // ноля нет вовсе
    return length(tl, tr) - countOfMinimum[v];          // вычли непокрытое
}

Ответ снимается только с корня, и это позволяет не проталкивать пометки вовсе: прибавление на отрезке меняет минимум узла, а корень пересчитывается снизу вверх. Такое дерево короче обычного ленивого.

Границы полуоткрытые ($[y_1, y_2)$), иначе прямоугольники, соприкасающиеся стороной, посчитаются с лишней линией нулевой площади — а на целочисленной сетке эта линия внезапно окажется ненулевой.

Точки в прямоугольнике

Офлайн-задача: даны точки и запросы-прямоугольники, для каждого нужно количество точек внутри.

Запрос раскладывается на два префиксных: количество в $[1, x_2]$ минус количество в $[1, x_1 - 1]$, каждое с ограничением по $y$. Сортируем и точки, и половинки запросов по $x$, идём слева направо, добавляем точки в дерево по $y$ и в момент половинки берём сумму на $[y_1, y_2]$.

Здесь дерево — обычное, с точечным прибавлением и суммой на отрезке, то есть дерево по значениям в чистом виде. Вся сложность задачи ушла в сортировку событий.

Признак, по которому узнаётся приём

В условии два измерения, и по одному из них объекты — отрезки, а не точки. Тогда это измерение становится осью времени, отрезки — парами событий, а дерево живёт по второму измерению.