This documentation is automatically generated by competitive-verifier/competitive-verifier
// 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";
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 |
![]() |
5 ms | 4 MB |
g++ | random_00 |
![]() |
54 ms | 5 MB |
g++ | random_01 |
![]() |
43 ms | 4 MB |
g++ | random_02 |
![]() |
65 ms | 5 MB |
g++ | random_03 |
![]() |
189 ms | 6 MB |
g++ | random_04 |
![]() |
120 ms | 6 MB |
g++ | random_05 |
![]() |
128 ms | 6 MB |
g++ | small_n_00 |
![]() |
29 ms | 5 MB |
g++ | small_n_01 |
![]() |
30 ms | 5 MB |
g++ | small_n_02 |
![]() |
31 ms | 5 MB |
g++ | small_q_00 |
![]() |
18 ms | 4 MB |
clang++ | example_00 |
![]() |
5 ms | 4 MB |
clang++ | random_00 |
![]() |
76 ms | 5 MB |
clang++ | random_01 |
![]() |
80 ms | 4 MB |
clang++ | random_02 |
![]() |
110 ms | 5 MB |
clang++ | random_03 |
![]() |
319 ms | 6 MB |
clang++ | random_04 |
![]() |
251 ms | 6 MB |
clang++ | random_05 |
![]() |
239 ms | 6 MB |
clang++ | small_n_00 |
![]() |
31 ms | 5 MB |
clang++ | small_n_01 |
![]() |
32 ms | 5 MB |
clang++ | small_n_02 |
![]() |
31 ms | 5 MB |
clang++ | small_q_00 |
![]() |
16 ms | 4 MB |