Поиск в std::set с откатами: как реализовать структуру с rollback на отсортированном множестве?

Откаты (rollback) удобно делать, когда операции образуют стек: ты только добавляешь (или делаешь обратимые изменения), запоминаешь, что сделал, и при откате применяешь обратное в обратном порядке. Это паттерн «DSU с откатами / структура только на add + rollback».

Если нужна именно отсортированная структура с бинпоиском и откатами, простой рабочий приём — журнал операций:

std::set<int> s;
std::vector<int> log; // что добавили (для отката удалить)

void add(int x) {
    auto [it, inserted] = s.insert(x);
    if (inserted) log.push_back(x); // помним только реально вставленное
    else log.push_back(INT_MIN);    // ничего не вставили — нечего откатывать
}
int checkpoint() { return (int)log.size(); }
void rollback(int cp) {
    while ((int)log.size() > cp) {
        int x = log.back(); log.pop_back();
        if (x != INT_MIN) s.erase(x);
    }
}

Каждая операция O(log n), откат до чекпоинта — O(числа откатываемых операций * log n). Память O(n).

Ключевой принцип: rollback дёшев, только если все изменения обратимы и сделаны стеково. Поэтому в offline-D&C по времени мы спускаемся в рекурсию, добавляя элементы, активные на текущем сегменте времени, делаем запросы, а на выходе из рекурсии откатываем ровно то, что добавили на этом уровне. Балансировки/перевешивания внутри set делать нельзя «руками» — поэтому либо std::set с журналом удалений (как выше), либо для агрегатов (сумма/максимум/связность) — DSU с откатами без сжатия путей, но с ранговой эвристикой, где каждый union обратим за O(1).