test/mo/rollback_mo_static_range_mode_query.test.cpp

• View this file on GitHub
• Last update: 2026-02-28 01:07:59+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_mode_query

Depends on

• Rollback Mo (mo/rollback_mo.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_mode_query"

#include "mo/rollback_mo.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    std::copy_n(std::istream_iterator<int>(std::cin), N, A.begin());
    auto C = A;
    std::ranges::sort(C);
    C.erase(std::unique(C.begin(), C.end()), C.end());
    for (auto &a : A) {
        a = int(std::ranges::lower_bound(C, a) - C.begin());
    }
    RollbackMo mo(N);
    for (auto i = 0; i < Q; ++i) {
        int l, r;
        std::cin >> l >> r;
        mo.add(l, r);
    }
    auto best = 0, val = 0;
    std::vector<int> freq(C.size());
    std::vector<std::tuple<int, int, int>> history;
    std::vector<std::pair<int, int>> ans(Q);
    auto add = [&](int i) {
        auto a = A[i];
        history.emplace_back(best, val, a);
        ++freq[a];
        if (val < freq[a]) {
            best = a;
            val = freq[a];
        }
    };
    auto rollback = [&] {
        auto [b, v, a] = history.back();
        history.pop_back();
        best = b;
        val = v;
        --freq[a];
    };
    auto eval = [&](int i) { ans[i] = {C[best], val}; };
    mo.solve(add, rollback, eval);
    for (auto [mode, cnt] : ans) {
        std::cout << mode << " " << cnt << "\n";
    }
}

#line 1 "test/mo/rollback_mo_static_range_mode_query.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_mode_query"

#line 1 "mo/rollback_mo.hpp"



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

struct RollbackMo {
    explicit RollbackMo(int n) : n_(n) {}
    void add(int l, int r) { // [l, r)
        assert(0 <= l && l <= r && r <= n_);
        queries_.emplace_back(l, r);
    }
    void solve(auto add, auto rollback, auto eval) { solve(add, add, rollback, eval); }
    void solve(auto add_left, auto add_right, auto rollback, auto eval) {
        const auto q = int(queries_.size());
        if (q == 0) {
            return;
        }
        const auto b_num = int(std::sqrt(q));
        const auto b_sz = (n_ + b_num - 1) / b_num;
        std::vector<std::vector<int>> buckets((n_ - 1) / b_sz + 1);
        auto rollback_n = [&](int n) {
            for (auto i = 0; i < n; ++i) {
                rollback();
            }
        };
        auto naive = [&](int qid) {
            auto [l, r] = queries_[qid];
            for (auto i = l; i < r; ++i) {
                add_right(i);
            }
            eval(qid);
            rollback_n(r - l);
        };
        for (auto qid = 0; qid < q; ++qid) {
            auto [l, r] = queries_[qid];
            auto il = l / b_sz, ir = r / b_sz;
            if (il == ir) {
                naive(qid);
            } else {
                buckets[il].push_back(qid);
            }
        }
        for (auto &bucket : buckets) {
            if (bucket.empty()) {
                continue;
            }
            std::ranges::sort(bucket, {}, [&](int i) { return queries_[i].second; });
            auto lmax = 0;
            for (auto qid : bucket) {
                auto [l, r] = queries_[qid];
                lmax = std::max(lmax, l);
            }
            auto l = lmax, r = lmax;
            for (auto qid : bucket) {
                auto [ql, qr] = queries_[qid];
                while (r < qr) {
                    add_right(r++);
                }
                while (ql < l) {
                    add_left(--l);
                }
                eval(qid);
                rollback_n(lmax - l);
                l = lmax;
            }
            rollback_n(r - l);
        }
    }

private:
    int n_;
    std::vector<std::pair<int, int>> queries_;
};


#line 4 "test/mo/rollback_mo_static_range_mode_query.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> A(N);
    std::copy_n(std::istream_iterator<int>(std::cin), N, A.begin());
    auto C = A;
    std::ranges::sort(C);
    C.erase(std::unique(C.begin(), C.end()), C.end());
    for (auto &a : A) {
        a = int(std::ranges::lower_bound(C, a) - C.begin());
    }
    RollbackMo mo(N);
    for (auto i = 0; i < Q; ++i) {
        int l, r;
        std::cin >> l >> r;
        mo.add(l, r);
    }
    auto best = 0, val = 0;
    std::vector<int> freq(C.size());
    std::vector<std::tuple<int, int, int>> history;
    std::vector<std::pair<int, int>> ans(Q);
    auto add = [&](int i) {
        auto a = A[i];
        history.emplace_back(best, val, a);
        ++freq[a];
        if (val < freq[a]) {
            best = a;
            val = freq[a];
        }
    };
    auto rollback = [&] {
        auto [b, v, a] = history.back();
        history.pop_back();
        best = b;
        val = v;
        --freq[a];
    };
    auto eval = [&](int i) { ans[i] = {C[best], val}; };
    mo.solve(add, rollback, eval);
    for (auto [mode, cnt] : ans) {
        std::cout << mode << " " << cnt << "\n";
    }
}

Back to top page