Запросы как события

Задача: даны $n$ отрезков и $q$ точек. Для каждой точки сказать, сколько отрезков её покрывает.

Отвечать на каждый запрос отдельно — $O(qn)$. Но если все запросы известны заранее, их можно встроить в тот же проход.

Такой подход называется офлайн-обработкой: мы читаем все запросы, переупорядочиваем их как нам удобно и отвечаем не в том порядке, в котором спросили.

Третий тип события

К открытиям и закрытиям добавляем события-запросы. Их тип — $0$: они не меняют баланс, а только читают его.

struct Event {
    long long x;
    int type;    // -1 открытие, 0 запрос, +1 закрытие
    int id;      // номер отрезка или номер запроса
};

Кодировка снова работает на нас: сортировка по типу сама расставляет события в правильном порядке — сначала все открытия, потом запросы, потом закрытия. Ровно то, что нужно для замкнутых отрезков: в точке стыка запрос должен увидеть максимальное покрытие.

И вычитание типа из баланса тоже не ломается: у запроса тип нулевой, баланс не меняется.

vector<int> answer(q);
int balance = 0;
for (const Event& e : events) {
    balance -= e.type;
    if (e.type == 0) answer[e.id] = balance;
}

Единственный if во всём цикле — и тот только чтобы записать ответ.

Сложность — $O((n + q) \log(n + q))$.

Почему порядок именно такой

Для замкнутых отрезков в точке $x$ должны быть учтены все отрезки, начинающиеся в $x$, и ещё не сброшены те, что в $x$ заканчиваются.

Значит: открытия → запрос → закрытия. Значения $-1, 0, +1$ дают это бесплатно.

Для полуинтервалов $[l, r)$ порядок другой: закрытия должны пройти до запроса. Тогда типы переставляют: закрытие $-1$, запрос $0$, открытие $+1$ — и меняют знак в изменении баланса.

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

Ответы в исходном порядке

Ключевая деталь офлайна: запросы обрабатываются не в том порядке, в котором пришли. Поэтому в событии обязательно хранить номер запроса, а ответы писать в массив по этому номеру.

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

Когда офлайн не подходит

Схема требует, чтобы все запросы были известны заранее. Это не всегда так.

Если задача интерактивная или следующий запрос зависит от ответа на предыдущий, переупорядочивать нельзя. Тогда нужна структура данных, отвечающая на запрос за логарифм: дерево Фенвика по сжатым координатам или дерево отрезков.

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

Тот же приём для сумм

Если вместо «сколько отрезков покрывает точку» спросить «какова сумма весов покрывающих отрезков», меняется одна строка: вместо $\pm 1$ баланс меняется на $\pm w_i$.

Так же считаются максимум и минимум по активным отрезкам — но там уже нужен multiset вместо счётчика, потому что удалять максимум из числа нельзя.

Общее правило: баланс работает, если операция обратима. Сумма обратима, максимум — нет. Та же граница, что у префиксных сумм.