test/Mo.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_count_distinct

Depends on

• Mo.cpp

Code

// 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";
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	random_00	AC	441 ms	14 MB
g++	random_01	AC	426 ms	13 MB
g++	random_02	AC	185 ms	10 MB
g++	random_03	AC	599 ms	15 MB
g++	random_04	AC	494 ms	15 MB
g++	random_05	AC	1072 ms	16 MB
g++	small_n_00	AC	96 ms	11 MB
g++	small_n_01	AC	102 ms	11 MB
g++	small_n_02	AC	107 ms	11 MB
g++	small_q_00	AC	74 ms	7 MB
clang++	example_00	AC	5 ms	4 MB
clang++	random_00	AC	483 ms	14 MB
clang++	random_01	AC	415 ms	14 MB
clang++	random_02	AC	167 ms	11 MB
clang++	random_03	AC	653 ms	15 MB
clang++	random_04	AC	491 ms	15 MB
clang++	random_05	AC	767 ms	16 MB
clang++	small_n_00	AC	97 ms	11 MB
clang++	small_n_01	AC	103 ms	11 MB
clang++	small_n_02	AC	106 ms	11 MB
clang++	small_q_00	AC	62 ms	7 MB

Back to top page