Algorithm-Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub UScuber/Algorithm-Library

:heavy_check_mark: test/yosupo/Data-Structure/Static-Range-Frequency.test.cpp

Depends on

Code

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

#include "../../../template/template.hpp"

#include "../../../data-structure/wavelet-matrix-comp.hpp"
#include "../../../others/fastIO.hpp"

int main(){
  int n,q;
  cin >> n >> q;
  vi a(n);
  rep(i, n) cin >> a[i];
  WaveletMatrixComp<int,19> mat(move(a));
  int l,r,x;
  while(q--){
    cin >> l >> r >> x;
    cout << mat.rank(x, r) - mat.rank(x, l) << '\n';
  }
}
#line 1 "test/yosupo/Data-Structure/Static-Range-Frequency.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_frequency"

#line 1 "template/template.hpp"
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <bitset>
#include <cctype>
#include <climits>
#include <functional>
#include <cassert>
#include <numeric>
#include <cstring>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define per(i, n) for(int i = (n) - 1; i >= 0; i--)
using ll = long long;
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
constexpr int mod = 1000000007;
using namespace std;
template<class T, class U>
bool chmax(T &a, const U &b){ return a < b ? (a = b, 1) : 0; }
template<class T, class U>
bool chmin(T &a, const U &b){ return a > b ? (a = b, 1) : 0; }
#line 4 "test/yosupo/Data-Structure/Static-Range-Frequency.test.cpp"

#line 1 "data-structure/bitvector.hpp"
struct BitVector {
  using uint = unsigned int;
  static constexpr int w = 32;
  #define rem(k) ((k) & (w - 1))
  int len, blocks;
  vector<uint> bit, sum;
  BitVector(){}
  BitVector(const int len) : len(len), blocks((len+w-1)/w){
    bit.assign(blocks, 0);
    sum.assign(blocks, 0);
  }
  inline void set(const int k, const int b = 1) noexcept{
    if(b) bit[k / w] |= 1U << rem(k);
    else bit[k / w] &= ~(1U << rem(k));
  }
  void build(){
    sum[0] = 0;
    for(int i = 1; i < blocks; i++){
      sum[i] = sum[i - 1] + __builtin_popcount(bit[i - 1]);
    }
  }
  int operator[](const int k) const{
    return bit[k / w] >> rem(k) & 1;
  }
  inline int rank(const int k) const noexcept{
    return sum[k / w] + __builtin_popcount(bit[k / w] & ((1U << rem(k)) - 1));
  }
  inline int rank(const int val, const int k) const noexcept{
    return val ? rank(k) : k - rank(k);
  }
  #undef rem
};
#line 2 "data-structure/wavelet-matrix.hpp"

//----- Wavelet Matrix -----


template <class T, int maxlog, bool USE_SUM = false>
struct WaveletMatrix {
  int len;
  BitVector matrix[maxlog];
  int mid[maxlog];
  vector<T> sum[maxlog];
  WaveletMatrix(){}
  WaveletMatrix(vector<T> v) : len(v.size()){
    vector<T> l(len), r(len);
		fill(matrix, matrix + maxlog, BitVector(len + 1));
    if(USE_SUM) fill(sum, sum + maxlog, vector<T>(len + 1));
    for(int level = maxlog - 1; level >= 0; level--){
      int left = 0, right = 0;
      for(int i = 0; i < len; i++){
        if(v[i] >> level & 1){
          matrix[level].set(i);
          r[right++] = v[i];
        }else{
          l[left++] = v[i];
        }
      }
      mid[level] = left;
      matrix[level].build();
      v.swap(l);
      copy(r.begin(), r.begin() + right, v.begin() + left);
      if(USE_SUM){
        sum[level][0] = 0;
        for(int i = 0; i < len; i++){
          sum[level][i + 1] = sum[level][i] + v[i];
        }
      }
    }
  }
  inline int succ(const int f, const int l, const int level) const{
    return matrix[level].rank(f, l) + mid[level] * f;
  }
  //find v[k]

  T access(int k) const{
    assert(0 <= k && k < len);
    T res = 0;
    for(int level = maxlog - 1; level >= 0; level--){
      const bool f = matrix[level][k];
      if(f) res |= T(1) << level;
      k = matrix[level].rank(f, k) + mid[level]*f;
    }
    return res;
  }
  T operator[](const int k) const{ return access(k); }
  // count i  (0 <= i < r) && v[i] == x

  int rank(const T x, int r) const{
    assert(0 <= r && r <= len);
    int l = 0;
    for(int level = maxlog - 1; level >= 0; level--){
      l = succ(x >> level & 1, l, level);
      r = succ(x >> level & 1, r, level);
    }
    return r - l;
  }
  //k-th value v[l,r)

  T kth_smallest(int l, int r, int k) const{
    assert(0 <= l && l <= r && r <= len);
    assert(0 <= k && k < r - l);
    T res = 0;
    for(int level = maxlog - 1; level >= 0; level--){
      int cnt = matrix[level].rank(0, r) - matrix[level].rank(0, l);
      bool f = cnt <= k;
      if(f){
        res |= T(1) << level;
        k -= cnt;
      }
      l = succ(f, l, level);
      r = succ(f, r, level);
    }
    return res;
  }
  T kth_largest(int l, int r, int k) const{
    return kth_smallest(l, r, r-l-k-1);
  }
  // sum of [0,k)th smallest elements([l, r))

  T kth_smallest_sum(int l, int r, int k) const{
    assert(0 <= l && l <= r && r <= len);
    assert(0 <= k && k <= r - l);
    assert(USE_SUM);
    T res = 0;
    for(int level = maxlog - 1; level >= 0; level--){
      const int l0 = matrix[level].rank(0, l);
      const int r0 = matrix[level].rank(0, r);
      if(k < r0 - l0){
        l = l0, r = r0;
      }else{
        k -= r0 - l0;
        res += sum[level][r0] - sum[level][l0];
        l += mid[level] - l0;
        r += mid[level] - r0;
      }
    }
    if(k) res += sum[0][l + k] - sum[0][l];
    return res;
  }
  // sum of [0,k)th largest elements([l, r))

  T kth_largest_sum(int l, int r, int k) const{
    assert(0 <= l && l <= r && r <= len);
    assert(0 <= k && k <= r - l);
    assert(USE_SUM);
    return  kth_smallest_sum(l, r, r - l) - kth_smallest_sum(l, r, r - l - k);
  }
  // count i  (l <= i < r), (v[i] < upper)

  int range_freq(int l, int r, const T upper) const{
    int res = 0;
    for(int level = maxlog - 1; level >= 0; level--){
      bool f = upper >> level & 1;
      if(f) res += matrix[level].rank(0, r) - matrix[level].rank(0, l);
      l = succ(f, l, level);
      r = succ(f, r, level);
    }
    return res;
  }
  // count i  (l <= i < r), (lower <= v[i] < upper)

  int range_freq(int l, int r, const T lower, const T upper) const{
    assert(0 <= l && l <= r && r <= len);
    return range_freq(l, r, upper) - range_freq(l, r, lower);
  }
  // max v[i]  (l <= i < r), (v[i] < upper)

  T prev_value(int l, int r, const T upper) const{
    assert(0 <= l && l <= r && r <= len);
    int cnt = range_freq(l, r, upper);
    return cnt == 0 ? -1 : kth_smallest(l, r, cnt - 1);
  }
  // min v[i]  (l <= i < r), (lower <= v[i])

  T next_value(int l, int r, const T lower) const{
    assert(0 <= l && l <= r && r <= len);
    int cnt = range_freq(l, r, lower);
    return cnt == r - l ? -1 : kth_smallest(l, r, cnt);
  }
};
#line 2 "data-structure/wavelet-matrix-comp.hpp"

//----- Compressed Wavelet Matrix -----


template <class T, int maxlog, bool USE_SUM = false>
struct WaveletMatrixComp {
  int len;
  BitVector matrix[maxlog];
  int mid[maxlog];
  vector<T> sum[maxlog];
  vector<T> d;
  WaveletMatrixComp(){}
  WaveletMatrixComp(const vector<T> &data) : len(data.size()), d(data){
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    vector<int> v(len);
    for(int i = 0; i < len; i++) v[i] = get_pos(data[i]);
    vector<int> l(len), r(len);
		fill(matrix, matrix + maxlog, BitVector(len + 1));
    if(USE_SUM) fill(sum, sum + maxlog, vector<T>(len + 1));
    for(int level = maxlog - 1; level >= 0; level--){
      int left = 0, right = 0;
      for(int i = 0; i < len; i++){
        if(v[i] >> level & 1){
          matrix[level].set(i);
          r[right++] = v[i];
        }else{
          l[left++] = v[i];
        }
      }
      mid[level] = left;
      matrix[level].build();
      v.swap(l);
      copy(r.begin(), r.begin() + right, v.begin() + left);
      if(USE_SUM){
        sum[level][0] = 0;
        for(int i = 0; i < len; i++){
          sum[level][i + 1] = sum[level][i] + d[v[i]];
        }
      }
    }
  }
  inline int get_pos(const T x) const{
		return lower_bound(d.begin(), d.end(), x) - d.begin();
	}
  inline int succ(const int f, const int l, const int level) const{
    return matrix[level].rank(f, l) + mid[level] * f;
  }
  //find v[k]

  T access(int k) const{
    assert(0 <= k && k < len);
    T res = 0;
    for(int level = maxlog - 1; level >= 0; level--){
      const bool f = matrix[level][k];
      if(f) res |= T(1) << level;
      k = matrix[level].rank(f, k) + mid[level]*f;
    }
    return d[res];
  }
  T operator[](const int k) const{ return access(k); }
  // count i  (0 <= i < r) && v[i] == x

  int rank(const T x, int r) const{
    assert(0 <= r && r <= len);
    const int pos = get_pos(x);
    if(pos >= (int)d.size() || d[pos] != x) return 0;
    int l = 0;
    for(int level = maxlog - 1; level >= 0; level--){
      l = succ(pos >> level & 1, l, level);
      r = succ(pos >> level & 1, r, level);
    }
    return r - l;
  }
  //k-th value v[l,r)

  T kth_smallest(int l, int r, int k) const{
    assert(0 <= l && l <= r && r <= len);
    assert(0 <= k && k < r - l);
    T res = 0;
    for(int level = maxlog - 1; level >= 0; level--){
      int cnt = matrix[level].rank(0, r) - matrix[level].rank(0, l);
      bool f = cnt <= k;
      if(f){
        res |= T(1) << level;
        k -= cnt;
      }
      l = succ(f, l, level);
      r = succ(f, r, level);
    }
    return d[res];
  }
  T kth_largest(int l, int r, int k) const{
    return kth_smallest(l, r, r-l-k-1);
  }
  // sum of [0,k)th smallest elements([l, r))

  T kth_smallest_sum(int l, int r, int k) const{
    assert(0 <= l && l <= r && r <= len);
    assert(0 <= k && k <= r - l);
    assert(USE_SUM);
    T res = 0;
    for(int level = maxlog - 1; level >= 0; level--){
      const int l0 = matrix[level].rank(0, l);
      const int r0 = matrix[level].rank(0, r);
      if(k < r0 - l0){
        l = l0, r = r0;
      }else{
        k -= r0 - l0;
        res += sum[level][r0] - sum[level][l0];
        l += mid[level] - l0;
        r += mid[level] - r0;
      }
    }
    if(k) res += sum[0][l + k] - sum[0][l];
    return res;
  }
  // sum of [0,k)th largest elements([l, r))

  T kth_largest_sum(int l, int r, int k) const{
    assert(0 <= l && l <= r && r <= len);
    assert(0 <= k && k <= r - l);
    assert(USE_SUM);
    return  kth_smallest_sum(l, r, r - l) - kth_smallest_sum(l, r, r - l - k);
  }
  // count i  (l <= i < r), (v[i] < upper)

  int range_freq(int l, int r, const T upper) const{
    const int pos = get_pos(upper);
    int res = 0;
    for(int level = maxlog - 1; level >= 0; level--){
      bool f = pos >> level & 1;
      if(f) res += matrix[level].rank(0, r) - matrix[level].rank(0, l);
      l = succ(f, l, level);
      r = succ(f, r, level);
    }
    return d[res];
  }
  // count i  (l <= i < r), (lower <= v[i] < upper)

  int range_freq(int l, int r, const T lower, const T upper) const{
    assert(0 <= l && l <= r && r <= len);
    return range_freq(l, r, upper) - range_freq(l, r, lower);
  }
  // max v[i]  (l <= i < r), (v[i] < upper)

  T prev_value(int l, int r, const T upper) const{
    assert(0 <= l && l <= r && r <= len);
    int cnt = range_freq(l, r, upper);
    return cnt == 0 ? -1 : kth_smallest(l, r, cnt - 1);
  }
  // min v[i]  (l <= i < r), (lower <= v[i])

  T next_value(int l, int r, const T lower) const{
    assert(0 <= l && l <= r && r <= len);
    int cnt = range_freq(l, r, lower);
    return cnt == r - l ? -1 : kth_smallest(l, r, cnt);
  }
};
#line 1 "others/fastIO.hpp"
namespace FastIO {
struct PreCalc {
  char num[10000 * 4];
  constexpr PreCalc() : num(){
    for(int i = 0; i < 10000; i++){
      int t = i;
      for(int j = 3; j >= 0; j--){
        num[i*4 + j] = (t % 10) + '0';
        t /= 10;
      }
    }
  }
};
static constexpr PreCalc pr;
struct FastIO {
  template <class T>
  using enable_if_integer = enable_if_t<is_integral<T>::value || is_same<T, __int128_t>::value || is_same<T, __uint128_t>::value>;
  static constexpr int buf_size = 1 << 20;
  static constexpr int rem = 1 << 6;
  char in_buf[buf_size], *in_cur = in_buf + buf_size;
  char out_buf[buf_size], *out_cur = out_buf;
  FastIO(){ load(); }
  ~FastIO(){ flush(); }
  void load(){
    const int len = in_buf + buf_size - in_cur;
    memmove(in_buf, in_cur, len);
    in_cur = in_buf;
    fread(in_buf + len, 1, buf_size - len, stdin);
  }
  void flush(){
    fwrite(out_buf, 1, out_cur - out_buf, stdout);
    out_cur = out_buf;
  }
  void through(){
    if(in_cur - in_buf >= buf_size - rem) load();
    while(*in_cur <= ' ') in_cur++;
    assert(in_buf <= in_cur && in_cur < in_buf + buf_size);
  }
  #define gc() (*in_cur++)
  template <class T, enable_if_integer<T>* = nullptr>
  inline void read(T &x){
    through();
    bool neg = false;
    int c = gc();
    if(c == '-') neg = true, c = gc();
    x = c^'0'; c = gc();
    while(c >= '0' && c <= '9') x = x*10 + (c^'0'), c = gc();
    if(neg) x = -x;
  }
  inline void read(string &x){
    through();
    x.clear();
    while(true){
      char *p = in_cur;
      while(*p > ' ' && p - in_buf < buf_size - rem) p++;
      copy(in_cur, p, back_inserter(x));
      in_cur = p;
      if(*p <= ' ') break;
      load();
    }
  }
  inline void read(char &x){
    through();
    x = gc();
  }
  #undef gc
  #define pc(c) *out_cur++ = (c)
  template <class T, enable_if_integer<T>* = nullptr>
  inline void out(T x){
    static constexpr int tmp_size = sizeof(T)*5/2;
    static char tmp[tmp_size];
    if(out_cur - out_buf >= buf_size - rem) flush();
    if(!x){ pc('0'); return; }
    if(x < 0){ pc('-'); x = -x; }
    int idx = tmp_size;
    while(x >= 10000){
      idx -= 4;
      memcpy(tmp + idx, pr.num + (x % 10000)*4, 4);
      x /= 10000;
    }
    if(x < 100){
      if(x < 10){
        pc(x + '0');
      }else{
        pc(x/10 + '0');
        pc(x%10 + '0');
      }
    }else{
      if(x < 1000){
        memcpy(out_cur, pr.num + x*4 + 1, 3);
        out_cur += 3;
      }else{
        memcpy(out_cur, pr.num + x*4, 4);
        out_cur += 4;
      }
    }
    memcpy(out_cur, tmp + idx, tmp_size - idx);
    out_cur += tmp_size - idx;
  }
  inline void out(const string &s){
    flush();
    fwrite(s.c_str(), 1, s.size(), stdout);
  }
  inline void out(const char c){
    if(out_cur - out_buf >= buf_size - rem) flush();
    pc(c);
  }
  #undef pc
  template <class T>
  friend FastIO &operator>>(FastIO &io, T &x){
    io.read(x);
    return io;
  }
  template <class T>
  friend FastIO &operator<<(FastIO &io, const T &x){
    io.out(x);
    return io;
  }
};
FastIO io;
} // namespace FastIO

using FastIO::io;
#define cin io
#define cout io
#line 7 "test/yosupo/Data-Structure/Static-Range-Frequency.test.cpp"

int main(){
  int n,q;
  cin >> n >> q;
  vi a(n);
  rep(i, n) cin >> a[i];
  WaveletMatrixComp<int,19> mat(move(a));
  int l,r,x;
  while(q--){
    cin >> l >> r >> x;
    cout << mat.rank(x, r) - mat.rank(x, l) << '\n';
  }
}
Back to top page