Множество отрезков онлайн

Всё, что было до сих пор в этом разделе, — офлайн: события собираются, сортируются, обрабатываются одним проходом.

Иногда так нельзя. Отрезки приходят и уходят вперемешку с запросами, ответ нужен сразу. Тогда сортировка не спасает, а спасает set: он и хранит порядок, и умеет за логарифм находить ближайшего соседа.

Структура

Держим непересекающиеся полуинтервалы $[l, r)$ в map<long long, long long> — от начала к концу. Дополнительное соглашение: примыкающие отрезки склеены, то есть между соседями всегда есть дырка.

Такое представление каноническое: одному и тому же покрытию соответствует ровно один набор пар. Отсюда все проверки становятся сравнениями с соседями.

map<long long, long long> s;             // l -> r

auto find(long long x) {                 // отрезок, содержащий x, либо s.end()
    auto it = s.upper_bound(x);          // первый с началом строго больше x
    if (it == s.begin()) return s.end();
    --it;                                // кандидат: начало не больше x
    return it->second > x ? it : s.end();
}

Шаг upper_bound плюс --it — основной приём при работе с set. Прямого «найди последний элемент, не превосходящий $x$» в библиотеке нет, и делают именно так. Проверка it == s.begin() обязательна: без неё --it уходит за начало.

Добавление с поглощением

Новый отрезок может перекрыть или примкнуть к нескольким существующим. Их надо удалить, расширив границы:

void add(long long l, long long r) {
    if (l >= r) return;
    auto it = s.upper_bound(l);
    if (it != s.begin()) {               // сосед слева
        auto pr = prev(it);
        if (pr->second >= l) {           // пересекается или примыкает
            l = min(l, pr->first);
            r = max(r, pr->second);
            s.erase(pr);
        }
    }
    it = s.lower_bound(l);
    while (it != s.end() && it->first <= r) {
        r = max(r, it->second);
        it = s.erase(it);                // erase возвращает следующий
    }
    s[l] = r;
}

Знак в pr->second >= l — не описка. Со строгим > отрезки $[1, 5)$ и $[5, 9)$ остались бы двумя, и представление перестало бы быть каноническим.

it = s.erase(it) — единственный корректный способ удалять во время обхода: обычный ++it после erase обратится к освобождённой памяти (подробности).

Сколько это стоит

Внутри add цикл, но каждая его итерация удаляет отрезок. Отрезок можно удалить только после того, как его добавили, поэтому суммарное число удалений не превосходит числа добавлений.

Итог: $O(\log n)$ амортизированно на операцию, хотя отдельный вызов может стоить линию. Ровно то же рассуждение, что для очереди на двух стеках и для стека ближайших меньших.

Проверено: 200 000 сценариев по 40 случайных операций; после каждой операции содержимое, каноничность (нет пустых отрезков, нет соприкасающихся) и результаты запросов сверялись с булевым массивом.

Где это нужно

Распределение памяти. Запросы: занять свободный блок длины $k$, освободить блок, сказать, где начинается блок, содержащий данную ячейку. Держим два множества — занятых и свободных отрезков; «занять» режет свободный, «освободить» добавляет и склеивает с соседями.

Укладка полосок. Даны отрезки $[x, x + w)$, надо разложить их по минимальному числу рядов так, чтобы в ряду они не пересекались. Идём по отрезкам и для каждого ищем первый ряд, где нет пересечения. В каждом ряду — своё множество занятых отрезков, проверка пересечения — один lower_bound.

Онлайн-объединение. Офлайн-версия сортирует события; здесь суммарная длина покрытия поддерживается прямо в add и remove — прибавляем длину нового, вычитаем длины поглощённых.

Родственный приём: множество «непокрытых»

Иногда отрезков нет вовсе, а есть множество позиций, и вопрос звучит как «все ли позиции на отрезке чем-то покрыты».

Задача про ладей: поле до $10^5 \times 10^5$, запросы «поставить ладью», «убрать ладью», «правда ли, что каждая клетка прямоугольника атакована». Ладья бьёт свою вертикаль и свою горизонталь целиком.

Клетка $(r, c)$ не атакована тогда и только тогда, когда пусты и строка $r$, и столбец $c$. Значит, прямоугольник атакован полностью, если все его строки заняты или все его столбцы заняты.

Держим счётчики ладей по строкам и по столбцам и два множества — пустых строк и пустых столбцов:

void put(int r, int c) {
    if (cntRow[r]++ == 0) freeRow.erase(r);
    if (cntCol[c]++ == 0) freeCol.erase(c);
}
void del(int r, int c) {
    if (--cntRow[r] == 0) freeRow.insert(r);
    if (--cntCol[c] == 0) freeCol.insert(c);
}
bool covered(int r1, int r2, int c1, int c2) {
    auto a = freeRow.lower_bound(r1);
    auto b = freeCol.lower_bound(c1);
    return (a == freeRow.end() || *a > r2)
        || (b == freeCol.end() || *b > c2);
}

Запрос — два lower_bound. Множество меняется только когда счётчик проходит через ноль, поэтому вставок и удалений не больше, чем самих запросов на изменение.

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

Общий признак приёма: хранить не то, что есть, а то, чего не хватает. Занятых линий может быть много, а вопрос «есть ли незанятая в диапазоне» отвечается одним поиском по множеству незанятых.

Когда set не нужен

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