test/src/range_query/static range_count_distinct/static_range_count_distinct.test.cpp

• View this file on GitHub
• Last update: 2024-01-30 19:29:32+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_count_distinct

Depends on

• Static range Count Distinct (library/range_query/static range_count_distinct.hpp)

Code

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

#include "library/range_query/static range_count_distinct.hpp"

#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    
    std::vector<int> a(n);
    for (int &e : a) std::cin >> e;

    suisen::StaticRangeCountDistinctOffline processor(a);
    processor.reserve(q);

    while (q--) {
        int l, r;
        std::cin >> l >> r;
        processor.add_query(l, r);
    }
    for (int ans : processor.solve()) {
        std::cout << ans << '\n';
    }
}

#line 1 "test/src/range_query/static range_count_distinct/static_range_count_distinct.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_count_distinct"

#line 1 "library/range_query/static range_count_distinct.hpp"



#include <cassert>
#include <cstdint>
#include <cstddef>
#include <unordered_map>
#include <utility>
#include <vector>

#include <atcoder/fenwicktree>

namespace suisen {
    struct StaticRangeCountDistinctOffline {
        StaticRangeCountDistinctOffline() : StaticRangeCountDistinctOffline(std::vector<int>{}) {}
        explicit StaticRangeCountDistinctOffline(const std::vector<int>& a) : _n(a.size()), _q(0), _a(a) {}

        void reserve(int q) { _qs.reserve(q); }

        // Return the ID of the given query (NOT the answer)
        int add_query(int l, int r) {
            assert(0 <= l and l <= r and r <= _n);
            _qs.emplace_back(l, r);
            return _q++;
        }

        std::vector<int> solve() const {
            // last[v] = 1 + max{ i | a[i]=v or i=-1 }
            std::unordered_map<int, int> last;
            // prv[i] = 1 + max{ j | a[i]=a[j] or j=-1 }
            std::vector<int> prv(_n);
            for (int i = 0; i < _n; ++i) {
                prv[i] = std::exchange(last[_a[i]], i + 1);
            }
            // sort ranges by bucket sort
            std::vector<int> index(_n + 2);
            for (auto& [l, r] : _qs) {
                ++index[r];
            }
            for (int i = 1; i <= _n; ++i) {
                index[i] += index[i - 1];
            }
            index[_n + 1] = _q;
            std::vector<int> qs_ord(_q);
            for (int qid = 0; qid < _q; ++qid) {
                qs_ord[--index[_qs[qid].second]] = qid;
            }

            atcoder::fenwick_tree<int> ft(_n + 1);
            std::vector<int> ans(_q);
            for (int r = 0; r <= _n; ++r) {
                for (int i = index[r]; i < index[r + 1]; ++i) {
                    const int qid = qs_ord[i], l = _qs[qid].first;
                    assert(_qs[qid].second == r);
                    ans[qid] = ft.sum(0, l + 1) - l;
                }
                if (r < _n) ft.add(prv[r], 1);
            }
            return ans;
        }

    private:
        int _n, _q;
        std::vector<int> _a;
        std::vector<std::pair<int, int>> _qs;
    };
} // namespace suisen


#line 4 "test/src/range_query/static range_count_distinct/static_range_count_distinct.test.cpp"

#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;
    
    std::vector<int> a(n);
    for (int &e : a) std::cin >> e;

    suisen::StaticRangeCountDistinctOffline processor(a);
    processor.reserve(q);

    while (q--) {
        int l, r;
        std::cin >> l >> r;
        processor.add_query(l, r);
    }
    for (int ans : processor.solve()) {
        std::cout << ans << '\n';
    }
}

Back to top page