test/Mo-Rollback.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_mode_query

Depends on

• Mo-Rollback.cpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_mode_query
#include "../Mo-Rollback.cpp"
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < n; i++)
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    auto xx = a;
    sort(all(xx));
    xx.erase(unique(all(xx)), xx.end());
    rep(i, n) a[i] = lower_bound(all(xx), a[i]) - xx.begin();
    MoRollback mo(n);
    rep(i, q) {
        int l, r;
        cin >> l >> r;
        mo.add(l, r);
    }
    using P = pair<int, int>;
    vector<P> ans(q);
    P res{0, -1};
    vector<int> cnt(xx.size());
    vector<int> history;
    P memo_res{0, -1};
    auto add = [&](int i) {
        history.push_back(a[i]);
        cnt[a[i]]++;
        res = max(res, P{cnt[a[i]], a[i]});
    };
    auto snapshot = [&]() {
        history.clear();
        memo_res = res;
    };
    auto rollback = [&]() {
        while (history.size()) {
            cnt[history.back()]--;
            history.pop_back();
        }
        res = memo_res;
    };
    auto clear = [&]() {
        res = memo_res = {0, -1};
        cnt.assign(xx.size(), 0);
        history.clear();
    };
    auto answer = [&](int i) { ans[i] = res; };
    mo.build(add, snapshot, rollback, clear, answer);
    rep(i, q) cout << xx[ans[i].second] << " " << ans[i].first << "\n";
}

#line 1 "test/Mo-Rollback.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_mode_query
#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();
        }
    }
};
#line 3 "test/Mo-Rollback.test.cpp"
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < n; i++)
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    auto xx = a;
    sort(all(xx));
    xx.erase(unique(all(xx)), xx.end());
    rep(i, n) a[i] = lower_bound(all(xx), a[i]) - xx.begin();
    MoRollback mo(n);
    rep(i, q) {
        int l, r;
        cin >> l >> r;
        mo.add(l, r);
    }
    using P = pair<int, int>;
    vector<P> ans(q);
    P res{0, -1};
    vector<int> cnt(xx.size());
    vector<int> history;
    P memo_res{0, -1};
    auto add = [&](int i) {
        history.push_back(a[i]);
        cnt[a[i]]++;
        res = max(res, P{cnt[a[i]], a[i]});
    };
    auto snapshot = [&]() {
        history.clear();
        memo_res = res;
    };
    auto rollback = [&]() {
        while (history.size()) {
            cnt[history.back()]--;
            history.pop_back();
        }
        res = memo_res;
    };
    auto clear = [&]() {
        res = memo_res = {0, -1};
        cnt.assign(xx.size(), 0);
        history.clear();
    };
    auto answer = [&](int i) { ans[i] = res; };
    mo.build(add, snapshot, rollback, clear, answer);
    rep(i, q) cout << xx[ans[i].second] << " " << ans[i].first << "\n";
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	random_00	AC	54 ms	5 MB
g++	random_01	AC	43 ms	4 MB
g++	random_02	AC	65 ms	5 MB
g++	random_03	AC	189 ms	6 MB
g++	random_04	AC	120 ms	6 MB
g++	random_05	AC	128 ms	6 MB
g++	small_n_00	AC	29 ms	5 MB
g++	small_n_01	AC	30 ms	5 MB
g++	small_n_02	AC	31 ms	5 MB
g++	small_q_00	AC	18 ms	4 MB
clang++	example_00	AC	5 ms	4 MB
clang++	random_00	AC	76 ms	5 MB
clang++	random_01	AC	80 ms	4 MB
clang++	random_02	AC	110 ms	5 MB
clang++	random_03	AC	319 ms	6 MB
clang++	random_04	AC	251 ms	6 MB
clang++	random_05	AC	239 ms	6 MB
clang++	small_n_00	AC	31 ms	5 MB
clang++	small_n_01	AC	32 ms	5 MB
clang++	small_n_02	AC	31 ms	5 MB
clang++	small_q_00	AC	16 ms	4 MB

Back to top page