区間の値の種類数
(library/sequence/static_range_count_distinct.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/sequence/static_range_count_distinct.hpp"

区間の値の種類数

できること

• 静的な配列に対して、指定された範囲 $[l, r)$ 内の値が何種類かを求める
• 先にクエリをすべて読むオフラインクエリ
• 座標圧縮+FenwickTreeで「その位置の値が今の右端 $i$ から見て『最後に現れた位置』かどうか」を求める

計算量

$O((N + Q) \log N)$

使い方

vector<int> A = {1, 2, 1, 3, 2, 4, 4, 1}; 
// インデックス:  0  1  2  3  4  5  6  7

StaticRangeCountDistinct srcd(A);

// クエリの登録: [l, r) の半開区間で指定
// 例1: A[0...3] -> {1, 2, 1} は 2種類 {1, 2}
srcd.add_query(0, 3); 
// 例2: A[2...5] -> {1, 3, 2} は 3種類 {1, 2, 3}
srcd.add_query(2, 5); 
// 例3: A[5...7] -> {4, 4} は 1種類 {4}
srcd.add_query(5, 7);
// 例4: A[0...8] -> 全体 {1, 2, 1, 3, 2, 4, 4, 1} は 4種類 {1, 2, 3, 4}
srcd.add_query(0, 8);

// 計算実行
vector<size_t> results = srcd.calculate_queries();

// 結果の表示サンプル
vector<string> labels = {"[0, 3)", "[2, 5)", "[5, 7)", "[0, 8)"};
for (int i = 0; i < (int)results.size(); ++i) {
    cout << "Range " << labels[i] << " Distinct Count: " << results[i] << endl;
}

Depends on

• Fenwick Tree (library/segtree/fenwick_tree.hpp)
• 座標圧縮 (library/sequence/compressor.hpp)

Verified with

• 区間の値の種類数のテスト (tests/sequence.static_range_count_distinct.test.cpp)

Code

#pragma once
#include "library/segtree/fenwick_tree.hpp"
#include "library/sequence/compressor.hpp"
template <typename T> struct StaticRangeCountDistinct {
  private:
    size_t m;
    vector<int> xs;
    vector<vector<int>> mp;
    vector<pair<int, int>> qs;

  public:
    explicit StaticRangeCountDistinct(const vector<T> &vs) : xs(vs.size()) {
        Compressor<T> comp(vs);
        m = comp.size();
        xs = comp.get_all();
    }
    void add_query(int l, int r) {
        assert(0ll <= l and l <= r and r <= (int)xs.size());
        qs.emplace_back(l, r - 1);
    }
    vector<size_t> calclate_queries() const {
        int n = (int)xs.size();
        int q = (int)qs.size();
        vector<vector<int>> ev(n);
        for (int i = 0; i < q; ++i) {
            if (qs[i].first <= qs[i].second) {
                ev[qs[i].second].emplace_back(i);
            }
        }
        vector<int> pre(m, -1);
        FenwickTree fwk(n);
        vector<size_t> ans(q);
        for (int i = 0; i < n; ++i) {
            int v = xs[i];
            if (~pre[v]) fwk.add(n - pre[v] - 1, -1);
            pre[v] = i;
            fwk.add(n - i - 1, 1);
            for (auto &&j : ev[i]) {
                ans[j] = fwk.sum(n - qs[j].first - 1);
            }
        }
        return ans;
    }
};

#line 2 "library/segtree/fenwick_tree.hpp"
struct FenwickTree {
  private:
    int N;
    vector<int> fwk;

  public:
    FenwickTree(int N) : N(N) { fwk.assign(N + 1, 0); }
    FenwickTree(const vector<int> &A) : N(A.size()) {
        fwk.assign(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            fwk[i] += A[i - 1];
            if (i + (i & -i) <= N) fwk[i + (i & -i)] += fwk[i];
        }
    }
    void add(int i, const int &x) {
        for (++i; i <= N; i += i & -i) fwk[i] += x;
    }
    int sum(int i) {
        int ans = 0;
        for (++i; i; i -= i & -i) ans += fwk[i];
        return ans;
    }
};
#line 2 "library/sequence/compressor.hpp"
template <typename T> struct Compressor {
    vector<T> origin, dict;
    Compressor(const vector<T> &v) : origin(v), dict(v) {
        sort(dict.begin(), dict.end());
        dict.erase(unique(dict.begin(), dict.end()), dict.end());
    }
    int size() const { return dict.size(); }
    // 値 -> ID (圧縮)
    int get_id(T x) const {
        return lower_bound(dict.begin(), dict.end(), x) - dict.begin();
    }
    // 値 -> ID (upper_bound版)
    int get_upper_id(T x) const {
        return upper_bound(dict.begin(), dict.end(), x) - dict.begin();
    }
    // ID -> 値 (復元)
    T get_val(int id) const { return dict[id]; }
    // すべて圧縮
    vector<int> get_all() {
        vector<int> res;
        for (auto &&x : origin) res.emplace_back(get_id(x));
        return res;
    }
};
#line 4 "library/sequence/static_range_count_distinct.hpp"
template <typename T> struct StaticRangeCountDistinct {
  private:
    size_t m;
    vector<int> xs;
    vector<vector<int>> mp;
    vector<pair<int, int>> qs;

  public:
    explicit StaticRangeCountDistinct(const vector<T> &vs) : xs(vs.size()) {
        Compressor<T> comp(vs);
        m = comp.size();
        xs = comp.get_all();
    }
    void add_query(int l, int r) {
        assert(0ll <= l and l <= r and r <= (int)xs.size());
        qs.emplace_back(l, r - 1);
    }
    vector<size_t> calclate_queries() const {
        int n = (int)xs.size();
        int q = (int)qs.size();
        vector<vector<int>> ev(n);
        for (int i = 0; i < q; ++i) {
            if (qs[i].first <= qs[i].second) {
                ev[qs[i].second].emplace_back(i);
            }
        }
        vector<int> pre(m, -1);
        FenwickTree fwk(n);
        vector<size_t> ans(q);
        for (int i = 0; i < n; ++i) {
            int v = xs[i];
            if (~pre[v]) fwk.add(n - pre[v] - 1, -1);
            pre[v] = i;
            fwk.add(n - i - 1, 1);
            for (auto &&j : ev[i]) {
                ans[j] = fwk.sum(n - qs[j].first - 1);
            }
        }
        return ans;
    }
};

Back to top page