Static Range Count Distinct (区間の値の種類数) (other/static-range-count-distinct.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-08-10 03:11:07+09:00
• Include: #include "other/static-range-count-distinct.hpp"

数列が与えられたときに、区間の値の種類数を求めるクエリを処理します。

コンストラクタ

StaticRangeCountDistinct< T >(const vector<T> &vs)

数列を vs で初期化します。

T は vs の各要素の型です。

計算量

• $O(n)$

add_query

void add_query(int l, int r)

$vs[l, r)$ に現れる値の種類数を求めるクエリを追加します。

制約

• $0 \leq l \leq r \leq n$

計算量

• $O(1)$

calculate_queries

vector< size_t > calclate_queries() const

それぞれのクエリの答えを返します。$i$ 番目の要素は $i$ 番目に追加したクエリの答えが格納されます。

計算量

• $O((n + q) \log n)$

Depends on

• Binary Indexed Tree (structure/others/binary-indexed-tree.hpp)

Verified with

• test/verify/yosupo-static-range-count-distinct.test.cpp

Code

#include "../structure/others/binary-indexed-tree.hpp"

template <typename T>
struct StaticRangeCountDistinct {
 private:
  using BIT = BinaryIndexedTree<int>;
  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()) {
    vector<T> ys = vs;
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    m = ys.size();
    for (int i = 0; i < vs.size(); i++) {
      int p = lower_bound(ys.begin(), ys.end(), vs[i]) - ys.begin();
      xs[i] = p;
    }
  }

  void add_query(int l, int r) {
    assert(0 <= l and l <= r and r <= 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);
    BIT bit(n);
    vector<size_t> ans(q);
    for (int i = 0; i < n; i++) {
      int v = xs[i];
      if (~pre[v]) bit.apply(n - pre[v] - 1, -1);
      pre[v] = i;
      bit.apply(n - i - 1, 1);
      for (auto &j : ev[i]) {
        ans[j] = bit.prod(n - qs[j].first);
      }
    }
    return ans;
  }
};

#line 1 "structure/others/binary-indexed-tree.hpp"
template <typename T>
struct BinaryIndexedTree {
 private:
  int n;
  vector<T> data;

 public:
  BinaryIndexedTree() = default;

  explicit BinaryIndexedTree(int n) : n(n) { data.assign(n + 1, T()); }

  explicit BinaryIndexedTree(const vector<T> &v)
      : BinaryIndexedTree((int)v.size()) {
    build(v);
  }

  void build(const vector<T> &v) {
    assert(n == (int)v.size());
    for (int i = 1; i <= n; i++) data[i] = v[i - 1];
    for (int i = 1; i <= n; i++) {
      int j = i + (i & -i);
      if (j <= n) data[j] += data[i];
    }
  }

  void apply(int k, const T &x) {
    for (++k; k <= n; k += k & -k) data[k] += x;
  }

  T prod(int r) const {
    T ret = T();
    for (; r > 0; r -= r & -r) ret += data[r];
    return ret;
  }

  T prod(int l, int r) const { return prod(r) - prod(l); }

  int lower_bound(T x) const {
    int i = 0;
    for (int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
      if (i + k <= n && data[i + k] < x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }

  int upper_bound(T x) const {
    int i = 0;
    for (int k = 1 << (__lg(n) + 1); k > 0; k >>= 1) {
      if (i + k <= n && data[i + k] <= x) {
        x -= data[i + k];
        i += k;
      }
    }
    return i;
  }
};
#line 2 "other/static-range-count-distinct.hpp"

template <typename T>
struct StaticRangeCountDistinct {
 private:
  using BIT = BinaryIndexedTree<int>;
  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()) {
    vector<T> ys = vs;
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    m = ys.size();
    for (int i = 0; i < vs.size(); i++) {
      int p = lower_bound(ys.begin(), ys.end(), vs[i]) - ys.begin();
      xs[i] = p;
    }
  }

  void add_query(int l, int r) {
    assert(0 <= l and l <= r and r <= 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);
    BIT bit(n);
    vector<size_t> ans(q);
    for (int i = 0; i < n; i++) {
      int v = xs[i];
      if (~pre[v]) bit.apply(n - pre[v] - 1, -1);
      pre[v] = i;
      bit.apply(n - i - 1, 1);
      for (auto &j : ev[i]) {
        ans[j] = bit.prod(n - qs[j].first);
      }
    }
    return ans;
  }
};

Back to top page