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

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-10 07:26:44+00: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

#pragma once

#include <algorithm>
#include <cstddef>
#include <vector>

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

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

#line 2 "other/static-range-frequency.hpp"

#include <algorithm>
#include <cstddef>
#include <vector>

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

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

Back to top page