Static Range Frequency (区間の値の出現回数) (other/static-range-frequency.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-27 02:13:15+09:00
• Include: #include "other/static-range-frequency.hpp"

数列が与えられたときに、ある値が出現する回数を求めるクエリを処理します。

コンストラクタ

StaticRangeFrequency< T >(const vector<T> &xs)

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

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

計算量

• $O(n \log n)$

query

size_t query(int l, int r, T x) const

$xs[l, r)$ に $x$ が出現する回数を返します。

制約

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

計算量

• $O(\log n)$

Verified with

• test/verify/yosupo-static-range-frequency.test.cpp

Code

template <typename T>
struct StaticRangeFrequency {
 private:
  vector<T> vs;
  vector<vector<int> > mp;

 public:
  explicit StaticRangeFrequency(const vector<T> &xs) : vs{xs} {
    sort(vs.begin(), vs.end());
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    mp.resize(vs.size());
    for (int i = 0; i < xs.size(); i++) {
      int p = lower_bound(vs.begin(), vs.end(), xs[i]) - vs.begin();
      mp[p].emplace_back(i);
    }
  }
  size_t query(int l, int r, T x) const {
    int p = lower_bound(vs.begin(), vs.end(), x) - vs.begin();
    if (p == vs.size() or x != vs[p]) return 0;
    l = lower_bound(mp[p].begin(), mp[p].end(), l) - vs.begin();
    r = lower_bound(mp[p].begin(), mp[p].end(), r) - vs.begin();
    return r - l;
  }
};

#line 1 "other/static-range-frequency.hpp"
template <typename T>
struct StaticRangeFrequency {
 private:
  vector<T> vs;
  vector<vector<int> > mp;

 public:
  explicit StaticRangeFrequency(const vector<T> &xs) : vs{xs} {
    sort(vs.begin(), vs.end());
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    mp.resize(vs.size());
    for (int i = 0; i < xs.size(); i++) {
      int p = lower_bound(vs.begin(), vs.end(), xs[i]) - vs.begin();
      mp[p].emplace_back(i);
    }
  }
  size_t query(int l, int r, T x) const {
    int p = lower_bound(vs.begin(), vs.end(), x) - vs.begin();
    if (p == vs.size() or x != vs[p]) return 0;
    l = lower_bound(mp[p].begin(), mp[p].end(), l) - vs.begin();
    r = lower_bound(mp[p].begin(), mp[p].end(), r) - vs.begin();
    return r - l;
  }
};

Back to top page