This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_count_distinct
#include "../Mo.cpp"
int cnt[500010];
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
auto xx = a;
sort(xx.begin(), xx.end());
xx.erase(unique(xx.begin(), xx.end()), xx.end());
for (int i = 0; i < n; i++) a[i] = lower_bound(xx.begin(), xx.end(), a[i]) - xx.begin();
int ans = 0;
vector<int> out(q);
auto add = [&](int i) {
cnt[a[i]]++;
if (cnt[a[i]] == 1) ans++;
};
auto erase = [&](int i) {
if (cnt[a[i]] == 1) ans--;
cnt[a[i]]--;
};
auto answer = [&](int i) { out[i] = ans; };
Mo mo(n);
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
mo.add(l, r);
}
mo.build(add, erase, answer);
for (int i = 0; i < q; i++) cout << out[i] << "\n";
}
#line 1 "test/Mo.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_count_distinct
#line 1 "Mo.cpp"
#include <bits/stdc++.h>
using namespace std;
struct Mo {
int n;
vector<pair<int, int>> lr;
explicit Mo(int n) : n(n) {}
void add(int l, int r) { /* [l, r) */ lr.emplace_back(l, r); }
template <typename AL, typename AR, typename EL, typename ER, typename O>
void build(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) {
int q = (int)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 (ablock & 1) ? lr[a].second > lr[b].second : lr[a].second < lr[b].second;
});
int l = 0, r = 0;
for (auto idx : ord) {
while (l > lr[idx].first) add_left(--l);
while (r < lr[idx].second) add_right(r++);
while (l < lr[idx].first) erase_left(l++);
while (r > lr[idx].second) erase_right(--r);
out(idx);
}
}
template <typename A, typename E, typename O>
void build(const A &add, const E &erase, const O &out) {
build(add, add, erase, erase, out);
}
};
#line 3 "test/Mo.test.cpp"
int cnt[500010];
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
auto xx = a;
sort(xx.begin(), xx.end());
xx.erase(unique(xx.begin(), xx.end()), xx.end());
for (int i = 0; i < n; i++) a[i] = lower_bound(xx.begin(), xx.end(), a[i]) - xx.begin();
int ans = 0;
vector<int> out(q);
auto add = [&](int i) {
cnt[a[i]]++;
if (cnt[a[i]] == 1) ans++;
};
auto erase = [&](int i) {
if (cnt[a[i]] == 1) ans--;
cnt[a[i]]--;
};
auto answer = [&](int i) { out[i] = ans; };
Mo mo(n);
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
mo.add(l, r);
}
mo.build(add, erase, answer);
for (int i = 0; i < q; i++) cout << out[i] << "\n";
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 |
![]() |
5 ms | 4 MB |
g++ | random_00 |
![]() |
441 ms | 14 MB |
g++ | random_01 |
![]() |
426 ms | 13 MB |
g++ | random_02 |
![]() |
185 ms | 10 MB |
g++ | random_03 |
![]() |
599 ms | 15 MB |
g++ | random_04 |
![]() |
494 ms | 15 MB |
g++ | random_05 |
![]() |
1072 ms | 16 MB |
g++ | small_n_00 |
![]() |
96 ms | 11 MB |
g++ | small_n_01 |
![]() |
102 ms | 11 MB |
g++ | small_n_02 |
![]() |
107 ms | 11 MB |
g++ | small_q_00 |
![]() |
74 ms | 7 MB |
clang++ | example_00 |
![]() |
5 ms | 4 MB |
clang++ | random_00 |
![]() |
483 ms | 14 MB |
clang++ | random_01 |
![]() |
415 ms | 14 MB |
clang++ | random_02 |
![]() |
167 ms | 11 MB |
clang++ | random_03 |
![]() |
653 ms | 15 MB |
clang++ | random_04 |
![]() |
491 ms | 15 MB |
clang++ | random_05 |
![]() |
767 ms | 16 MB |
clang++ | small_n_00 |
![]() |
97 ms | 11 MB |
clang++ | small_n_01 |
![]() |
103 ms | 11 MB |
clang++ | small_n_02 |
![]() |
106 ms | 11 MB |
clang++ | small_q_00 |
![]() |
62 ms | 7 MB |