Mo-Rollback.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00

Verified with

• test/Mo-Rollback.test.cpp

Code

#include <bits/stdc++.h>
using namespace std;
struct MoRollback {
    int n;
    vector<pair<int, int>> lr;
    MoRollback(int n) : n(n) {}
    void add(int l, int r) { /* [l, r) */ lr.emplace_back(l, r); }
    template <typename A, typename S, typename R, typename C, typename O>
    void build(const A& add, const S& snapshot, const R& rollback, const C& clear, const O& out) {
        int q = lr.size();
        int bs = max<int>(1, sqrt(n));
        vector<int> ord(q);
        iota(begin(ord), end(ord), 0);
        sort(begin(ord), end(ord), [&](int a, int b) {
            int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
            if (ablock != bblock) return ablock < bblock;
            return lr[a].second < lr[b].second;
        });
        int l = bs, r = bs;
        for (auto idx : ord) {
            while (lr[idx].first >= l) {
                clear();
                l += bs;
                r = l;
            }
            if (lr[idx].second < l) {
                clear();
                for (int i = lr[idx].first; i < lr[idx].second; i++) add(i);
                out(idx);
                for (int i = lr[idx].first; i < lr[idx].second; i++) rollback();
                continue;
            }
            while (r < lr[idx].second) add(r++);
            snapshot();
            for (int i = l - 1; i >= lr[idx].first; i--) add(i);
            out(idx);
            rollback();
        }
    }
};

#line 1 "Mo-Rollback.cpp"
#include <bits/stdc++.h>
using namespace std;
struct MoRollback {
    int n;
    vector<pair<int, int>> lr;
    MoRollback(int n) : n(n) {}
    void add(int l, int r) { /* [l, r) */ lr.emplace_back(l, r); }
    template <typename A, typename S, typename R, typename C, typename O>
    void build(const A& add, const S& snapshot, const R& rollback, const C& clear, const O& out) {
        int q = lr.size();
        int bs = max<int>(1, sqrt(n));
        vector<int> ord(q);
        iota(begin(ord), end(ord), 0);
        sort(begin(ord), end(ord), [&](int a, int b) {
            int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
            if (ablock != bblock) return ablock < bblock;
            return lr[a].second < lr[b].second;
        });
        int l = bs, r = bs;
        for (auto idx : ord) {
            while (lr[idx].first >= l) {
                clear();
                l += bs;
                r = l;
            }
            if (lr[idx].second < l) {
                clear();
                for (int i = lr[idx].first; i < lr[idx].second; i++) add(i);
                out(idx);
                for (int i = lr[idx].first; i < lr[idx].second; i++) rollback();
                continue;
            }
            while (r < lr[idx].second) add(r++);
            snapshot();
            for (int i = l - 1; i >= lr[idx].first; i--) add(i);
            out(idx);
            rollback();
        }
    }
};

Back to top page