ds/static_range_frequency.hpp

• View this file on GitHub
• Last update: 2024-08-26 01:20:39+09:00
• Include: #include "ds/static_range_frequency.hpp"

Depends on

• ds/hashmap.hpp
• ds/to_small_key.hpp

Verified with

• test/2_library_checker/data_structure/static_range_frequency.test.cpp

Code

#include "ds/to_small_key.hpp"

struct Static_Range_Frequency {
  vc<int> pos, indptr;
  To_Small_Key S;

  template <typename T>
  Static_Range_Frequency(vc<T>& A) {
    build(len(A), [&](int i) -> u64 { return A[i]; });
  }

  template <typename F>
  Static_Range_Frequency(int N, F f) {
    build(N, f);
  }

  template <typename F>
  void build(int N, F f) {
    S.reserve(N);
    pos.resize(N);
    vc<int> cnt(N + 1), dat(N);
    FOR(i, N) {
      u64 x = f(i);
      int k = S.set_key(x);
      cnt[1 + k]++, dat[i] = k;
    }
    FOR(k, N) cnt[1 + k] += cnt[k];
    indptr = cnt;
    FOR(i, N) pos[cnt[dat[i]]++] = i;
  }

  int query(int L, int R, u64 x) {
    int k = S.query(x);
    if (k == -1) return 0;
    int a = indptr[k], b = indptr[k + 1];
    auto nl = lower_bound(pos.begin() + a, pos.begin() + b, L);
    auto nr = lower_bound(pos.begin() + a, pos.begin() + b, R);
    return nr - nl;
  }
};

#line 1 "ds/static_range_frequency.hpp"

#line 2 "ds/hashmap.hpp"

// u64 -> Val

template <typename Val>
struct HashMap {
  // n は入れたいものの個数で ok

  HashMap(u32 n = 0) { build(n); }
  void build(u32 n) {
    u32 k = 8;
    while (k < n * 2) k *= 2;
    cap = k / 2, mask = k - 1;
    key.resize(k), val.resize(k), used.assign(k, 0);
  }

  // size を保ったまま. size=0 にするときは build すること.

  void clear() {
    used.assign(len(used), 0);
    cap = (mask + 1) / 2;
  }
  int size() { return len(used) / 2 - cap; }

  int index(const u64& k) {
    int i = 0;
    for (i = hash(k); used[i] && key[i] != k; i = (i + 1) & mask) {}
    return i;
  }

  Val& operator[](const u64& k) {
    if (cap == 0) extend();
    int i = index(k);
    if (!used[i]) { used[i] = 1, key[i] = k, val[i] = Val{}, --cap; }
    return val[i];
  }

  Val get(const u64& k, Val default_value) {
    int i = index(k);
    return (used[i] ? val[i] : default_value);
  }

  bool count(const u64& k) {
    int i = index(k);
    return used[i] && key[i] == k;
  }

  // f(key, val)

  template <typename F>
  void enumerate_all(F f) {
    FOR(i, len(used)) if (used[i]) f(key[i], val[i]);
  }

private:
  u32 cap, mask;
  vc<u64> key;
  vc<Val> val;
  vc<bool> used;

  u64 hash(u64 x) {
    static const u64 FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
    x += FIXED_RANDOM;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return (x ^ (x >> 31)) & mask;
  }

  void extend() {
    vc<pair<u64, Val>> dat;
    dat.reserve(len(used) / 2 - cap);
    FOR(i, len(used)) {
      if (used[i]) dat.eb(key[i], val[i]);
    }
    build(2 * len(dat));
    for (auto& [a, b]: dat) (*this)[a] = b;
  }
};
#line 2 "ds/to_small_key.hpp"

// [30,10,20,30] -> [0,1,2,0] etc.
struct To_Small_Key {
  int kind = 0;
  HashMap<int> MP;

  To_Small_Key(u32 n = 0) : MP(n) {}

  void reserve(u32 n) { MP.build(n); }

  int size() { return MP.size(); }

  int set_key(u64 x) {
    if (!MP.count(x)) MP[x] = kind++;
    return MP[x];
  }

  int query(u64 x) { return MP.get(x, -1); }
};
#line 3 "ds/static_range_frequency.hpp"

struct Static_Range_Frequency {
  vc<int> pos, indptr;
  To_Small_Key S;

  template <typename T>
  Static_Range_Frequency(vc<T>& A) {
    build(len(A), [&](int i) -> u64 { return A[i]; });
  }

  template <typename F>
  Static_Range_Frequency(int N, F f) {
    build(N, f);
  }

  template <typename F>
  void build(int N, F f) {
    S.reserve(N);
    pos.resize(N);
    vc<int> cnt(N + 1), dat(N);
    FOR(i, N) {
      u64 x = f(i);
      int k = S.set_key(x);
      cnt[1 + k]++, dat[i] = k;
    }
    FOR(k, N) cnt[1 + k] += cnt[k];
    indptr = cnt;
    FOR(i, N) pos[cnt[dat[i]]++] = i;
  }

  int query(int L, int R, u64 x) {
    int k = S.query(x);
    if (k == -1) return 0;
    int a = indptr[k], b = indptr[k + 1];
    auto nl = lower_bound(pos.begin() + a, pos.begin() + b, L);
    auto nr = lower_bound(pos.begin() + a, pos.begin() + b, R);
    return nr - nl;
  }
};

Back to top page