mo_with_updates.hpp

SECTIONData Structure INCLUDEnoya/ds/mo_with_updates.hpp

把区间询问与单点修改一起按三维 Mo 顺序处理；适合可增删元素且可前进、回退修改的离线题。

Complexity: Time: \(O(Q \log (Q + 1))\) sorting; \(O(Q B + N K + U K^{2})\) range/time moves, where \(B = \max (1 , \lfloor N^{2 / 3}\rfloor)\), \(K = \lfloor N / B\rfloor + 1\) and \(U\) is update count. Space: \(O(Q)\), excluding caller-owned values, updates and callback state.

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(Q log(Q+1)) sorting; O(Q B + N K + U K^2) range/time
/// moves, where B=max(1,floor(N^(2/3))), K=floor(N/B)+1 and U is update count.
/// Space: O(Q), excluding caller-owned values, updates and callback state.

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

namespace noya {

/// @brief Three-dimensional Mo scheduler for offline range queries mixed with
/// point updates; callbacks own the array and aggregate state.
struct mo_with_updates {
  struct query {
    int l = 0;
    int r = 0;
    int t = 0;
  };

  int n = 0;
  int nu = 0;
  std::vector<query> qs;

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

  /// @brief Record one update in chronological order and return its id.
  int add_update() { return nu++; }

  /// @brief Append [l, r) at the current update time and return its id.
  int add_query(int l, int r) {
    assert(0 <= l && l <= r && r <= n);
    int id = int(qs.size());
    qs.push_back({l, r, nu});
    return id;
  }

  /// @brief Process queries while moving a range and time cursor. The update
  /// callbacks receive (update_id, current_left, current_right).
  template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight,
            class ApplyUpdate, class RollbackUpdate, class Answer>
  void run(AddLeft al, AddRight ar, RemoveLeft dl, RemoveRight dr,
           ApplyUpdate ap, RollbackUpdate un, Answer ans) const {
    if (qs.empty()) {
      return;
    }
    int bs = std::max(1, int(std::pow(std::max(1, n), 2.0 / 3.0)));
    std::vector<int> ord(qs.size());
    std::iota(ord.begin(), ord.end(), 0);
    std::vector<std::tuple<int, int, int>> key(qs.size());
    for (int i = 0; i < int(qs.size()); ++i) {
      const query &a = qs[i];
      int lb = a.l / bs, rb = a.r / bs;
      key[i] = {lb, (lb & 1) ? -rb : rb, ((lb ^ rb) & 1) ? -a.t : a.t};
    }
    std::sort(ord.begin(), ord.end(),
              [&](int a, int b) { return key[a] < key[b]; });

    int l = 0;
    int r = 0;
    int t = 0;
    for (int id : ord) {
      const query &tar = qs[id];
      while (t < tar.t) {
        ap(t++, l, r);
      }
      while (tar.t < t) {
        un(--t, l, r);
      }
      while (tar.l < l) {
        al(--l);
      }
      while (r < tar.r) {
        ar(r++);
      }
      while (l < tar.l) {
        dl(l++);
      }
      while (tar.r < r) {
        dr(--r);
      }
      ans(id);
    }
  }
};

} // namespace noya

 // NOYA_MO_WITH_UPDATES_HPP

#ifndef NOYA_MO_WITH_UPDATES_HPP
#define NOYA_MO_WITH_UPDATES_HPP 1

/// @complexity Time: O(Q log(Q+1)) sorting; O(Q B + N K + U K^2) range/time
/// moves, where B=max(1,floor(N^(2/3))), K=floor(N/B)+1 and U is update count.
/// Space: O(Q), excluding caller-owned values, updates and callback state.

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

namespace noya {

/// @brief Three-dimensional Mo scheduler for offline range queries mixed with
/// point updates; callbacks own the array and aggregate state.
struct mo_with_updates {
  struct query {
    int l = 0;
    int r = 0;
    int t = 0;
  };

  int n = 0;
  int nu = 0;
  std::vector<query> qs;

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

  /// @brief Record one update in chronological order and return its id.
  int add_update() { return nu++; }

  /// @brief Append [l, r) at the current update time and return its id.
  int add_query(int l, int r) {
    assert(0 <= l && l <= r && r <= n);
    int id = int(qs.size());
    qs.push_back({l, r, nu});
    return id;
  }

  /// @brief Process queries while moving a range and time cursor. The update
  /// callbacks receive (update_id, current_left, current_right).
  template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight,
            class ApplyUpdate, class RollbackUpdate, class Answer>
  void run(AddLeft al, AddRight ar, RemoveLeft dl, RemoveRight dr,
           ApplyUpdate ap, RollbackUpdate un, Answer ans) const {
    if (qs.empty()) {
      return;
    }
    int bs = std::max(1, int(std::pow(std::max(1, n), 2.0 / 3.0)));
    std::vector<int> ord(qs.size());
    std::iota(ord.begin(), ord.end(), 0);
    std::vector<std::tuple<int, int, int>> key(qs.size());
    for (int i = 0; i < int(qs.size()); ++i) {
      const query &a = qs[i];
      int lb = a.l / bs, rb = a.r / bs;
      key[i] = {lb, (lb & 1) ? -rb : rb, ((lb ^ rb) & 1) ? -a.t : a.t};
    }
    std::sort(ord.begin(), ord.end(),
              [&](int a, int b) { return key[a] < key[b]; });

    int l = 0;
    int r = 0;
    int t = 0;
    for (int id : ord) {
      const query &tar = qs[id];
      while (t < tar.t) {
        ap(t++, l, r);
      }
      while (tar.t < t) {
        un(--t, l, r);
      }
      while (tar.l < l) {
        al(--l);
      }
      while (r < tar.r) {
        ar(r++);
      }
      while (l < tar.l) {
        dl(l++);
      }
      while (tar.r < r) {
        dr(--r);
      }
      ans(id);
    }
  }
};

} // namespace noya

#endif // NOYA_MO_WITH_UPDATES_HPP

/// @complexity Time: O(Q log(Q+1)) sorting; O(Q B + N K + U K^2) range/time
/// moves, where B=max(1,floor(N^(2/3))), K=floor(N/B)+1 and U is update count.
/// Space: O(Q), excluding caller-owned values, updates and callback state.

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

namespace noya {

/// @brief Three-dimensional Mo scheduler for offline range queries mixed with
/// point updates; callbacks own the array and aggregate state.
struct mo_with_updates {
  struct query {
    int l = 0;
    int r = 0;
    int t = 0;
  };

  int n = 0;
  int nu = 0;
  std::vector<query> qs;

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

  /// @brief Record one update in chronological order and return its id.
  int add_update() { return nu++; }

  /// @brief Append [l, r) at the current update time and return its id.
  int add_query(int l, int r) {
    assert(0 <= l && l <= r && r <= n);
    int id = int(qs.size());
    qs.push_back({l, r, nu});
    return id;
  }

  /// @brief Process queries while moving a range and time cursor. The update
  /// callbacks receive (update_id, current_left, current_right).
  template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight,
            class ApplyUpdate, class RollbackUpdate, class Answer>
  void run(AddLeft al, AddRight ar, RemoveLeft dl, RemoveRight dr,
           ApplyUpdate ap, RollbackUpdate un, Answer ans) const {
    if (qs.empty()) {
      return;
    }
    int bs = std::max(1, int(std::pow(std::max(1, n), 2.0 / 3.0)));
    std::vector<int> ord(qs.size());
    std::iota(ord.begin(), ord.end(), 0);
    std::vector<std::tuple<int, int, int>> key(qs.size());
    for (int i = 0; i < int(qs.size()); ++i) {
      const query &a = qs[i];
      int lb = a.l / bs, rb = a.r / bs;
      key[i] = {lb, (lb & 1) ? -rb : rb, ((lb ^ rb) & 1) ? -a.t : a.t};
    }
    std::sort(ord.begin(), ord.end(),
              [&](int a, int b) { return key[a] < key[b]; });

    int l = 0;
    int r = 0;
    int t = 0;
    for (int id : ord) {
      const query &tar = qs[id];
      while (t < tar.t) {
        ap(t++, l, r);
      }
      while (tar.t < t) {
        un(--t, l, r);
      }
      while (tar.l < l) {
        al(--l);
      }
      while (r < tar.r) {
        ar(r++);
      }
      while (l < tar.l) {
        dl(l++);
      }
      while (tar.r < r) {
        dr(--r);
      }
      ans(id);
    }
  }
};

} // namespace noya

 // NOYA_MO_WITH_UPDATES_HPP