rollback_mo.hpp

SECTIONData Structure INCLUDEnoya/rollback_mo.hpp

Offline half-open range scheduler for rollbackable add-only states. Each query uses add(position), snapshot(), rollback(token), and answer(id).

以回滚结构处理离线区间询问，避免删除操作；适合只能添加元素、但状态可以整体撤销的答案维护。

Implementation

View on GitHub

SourceExpanded

#ifndef NOYA_ROLLBACK_MO_HPP
#define NOYA_ROLLBACK_MO_HPP 1

/// @complexity Time: O((N + Q) sqrt(N)) add/rollback work with standard blocking.
/// Space: O(N + Q).

#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <utility>
#include <vector>

namespace noya {

/// @brief Offline half-open range scheduler for rollbackable add-only states.
/// Each query uses add(position), snapshot(), rollback(token), and answer(id).
struct rollback_mo {
  int n = 0;
  std::vector<std::pair<int, int>> queries;

  rollback_mo() = default;
  explicit rollback_mo(int n_) : n(n_) { assert(n >= 0); }

  int add_query(int left, int right) {
    assert(0 <= left && left <= right && right <= n);
    int id = int(queries.size());
    queries.emplace_back(left, right);
    return id;
  }

  template <class Add, class Snapshot, class Rollback, class Answer>
  void run(Add add, Snapshot snapshot, Rollback rollback, Answer answer) const {
    if (queries.empty()) {
      return;
    }
    int block_size = std::max(1, int(std::sqrt(std::max(1, n))));
    int block_count = (n + block_size - 1) / block_size + 1;
    std::vector<std::vector<int>> groups(block_count);
    auto initial = snapshot();

    for (int id = 0; id < int(queries.size()); id++) {
      auto [left, right] = queries[id];
      int block = left / block_size;
      int block_end = std::min(n, (block + 1) * block_size);
      if (right <= block_end) {
        auto token = snapshot();
        for (int position = left; position < right; position++) {
          add(position);
        }
        answer(id);
        rollback(token);
      } else {
        groups[block].push_back(id);
      }
    }

    for (int block = 0; block < block_count; block++) {
      auto &order = groups[block];
      if (order.empty()) {
        continue;
      }
      std::sort(order.begin(), order.end(), [&](int first, int second) {
        return queries[first].second < queries[second].second;
      });
      int block_end = std::min(n, (block + 1) * block_size);
      int right = block_end;
      for (int id : order) {
        auto [query_left, query_right] = queries[id];
        while (right < query_right) {
          add(right++);
        }
        auto token = snapshot();
        for (int position = block_end - 1; position >= query_left; position--) {
          add(position);
        }
        answer(id);
        rollback(token);
      }
      rollback(initial);
    }
  }
};

} // namespace noya

#endif // NOYA_ROLLBACK_MO_HPP

#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <utility>
#include <vector>

/// @complexity Time: O((N + Q) sqrt(N)) add/rollback work with standard blocking.
/// Space: O(N + Q).

namespace noya {

/// @brief Offline half-open range scheduler for rollbackable add-only states.
/// Each query uses add(position), snapshot(), rollback(token), and answer(id).
struct rollback_mo {
  int n = 0;
  std::vector<std::pair<int, int>> queries;

  rollback_mo() = default;
  explicit rollback_mo(int n_) : n(n_) { assert(n >= 0); }

  int add_query(int left, int right) {
    assert(0 <= left && left <= right && right <= n);
    int id = int(queries.size());
    queries.emplace_back(left, right);
    return id;
  }

  template <class Add, class Snapshot, class Rollback, class Answer>
  void run(Add add, Snapshot snapshot, Rollback rollback, Answer answer) const {
    if (queries.empty()) {
      return;
    }
    int block_size = std::max(1, int(std::sqrt(std::max(1, n))));
    int block_count = (n + block_size - 1) / block_size + 1;
    std::vector<std::vector<int>> groups(block_count);
    auto initial = snapshot();

    for (int id = 0; id < int(queries.size()); id++) {
      auto [left, right] = queries[id];
      int block = left / block_size;
      int block_end = std::min(n, (block + 1) * block_size);
      if (right <= block_end) {
        auto token = snapshot();
        for (int position = left; position < right; position++) {
          add(position);
        }
        answer(id);
        rollback(token);
      } else {
        groups[block].push_back(id);
      }
    }

    for (int block = 0; block < block_count; block++) {
      auto &order = groups[block];
      if (order.empty()) {
        continue;
      }
      std::sort(order.begin(), order.end(), [&](int first, int second) {
        return queries[first].second < queries[second].second;
      });
      int block_end = std::min(n, (block + 1) * block_size);
      int right = block_end;
      for (int id : order) {
        auto [query_left, query_right] = queries[id];
        while (right < query_right) {
          add(right++);
        }
        auto token = snapshot();
        for (int position = block_end - 1; position >= query_left; position--) {
          add(position);
        }
        answer(id);
        rollback(token);
      }
      rollback(initial);
    }
  }
};

} // namespace noya