ds/static_rmq.hpp

• View this file on GitHub
• Last update: 2024-02-11 04:08:39+09:00
• Include: #include "ds/static_rmq.hpp"

Depends on

• ds/sparse_table/sparse_table.hpp

Code

#include "ds/sparse_table/sparse_table.hpp"

// 構築 O(N), クエリ O(1)
template <typename Monoid>
struct Static_RMQ {
  using MX = Monoid;
  using X = typename MX::value_type;
  static constexpr int LOG = 4;
  int N, b_num;
  vc<X> A, pre, suf; // inclusive
  Sparse_Table<Monoid> ST;

  using u16 = unsigned short;
  vc<u16> dat;

  Static_RMQ() {}
  template <typename F>
  Static_RMQ(int n, F f) {
    build(n, f);
  }
  Static_RMQ(const vc<X>& v) { build(v); }

  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    N = m;
    b_num = N >> LOG;
    A.resize(N);
    FOR(i, N) A[i] = f(i);
    pre = A, suf = A;
    FOR(i, 1, N) {
      if (i & 15) pre[i] = MX::op(pre[i - 1], A[i]);
    }
    FOR_R(i, 1, N) {
      if (i & 15) suf[i - 1] = MX::op(A[i - 1], suf[i]);
    }
    ST.build(b_num, [&](int i) -> X { return suf[i << LOG]; });
    // 長さ 16 以下のクエリに対応するための前計算
    // [i,i+16) 内で i+j が [i,i+j] での最小値となる場合に j-th bit を立てる
    dat.resize(N);
    u32 stack = 0;
    FOR_R(i, N) {
      stack = (stack << 1) & 65535;
      while (stack) {
        int k = lowbit(stack);
        if (MX::op(A[i], A[i + k]) != A[i]) break;
        stack &= ~(u32(1) << k);
      }
      stack |= u32(1);
      dat[i] = stack;
    }
  }

  X prod(int L, int R) {
    assert(0 <= L && L <= R && R <= N);
    if (L == R) return MX::unit();
    if (R - L <= 16) {
      u32 d = dat[L] & ((u32(1) << (R - L)) - 1);
      return A[L + topbit(d)];
    }
    --R;
    int a = L >> LOG, b = R >> LOG;
    X x = ST.prod(a + 1, b);
    x = MX::op(suf[L], x);
    x = MX::op(x, pre[R]);
    return x;
  }
};

#line 2 "ds/sparse_table/sparse_table.hpp"

// 冪等なモノイドであることを仮定。disjoint sparse table より x 倍高速
template <class Monoid>
struct Sparse_Table {
  using MX = Monoid;
  using X = typename MX::value_type;
  int n, log;
  vvc<X> dat;

  Sparse_Table() {}
  Sparse_Table(int n) { build(n); }
  template <typename F>
  Sparse_Table(int n, F f) {
    build(n, f);
  }
  Sparse_Table(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::unit(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 1;
    while ((1 << log) < n) ++log;
    dat.resize(log);
    dat[0].resize(n);
    FOR(i, n) dat[0][i] = f(i);

    FOR(i, log - 1) {
      dat[i + 1].resize(len(dat[i]) - (1 << i));
      FOR(j, len(dat[i]) - (1 << i)) {
        dat[i + 1][j] = MX::op(dat[i][j], dat[i][j + (1 << i)]);
      }
    }
  }

  X prod(int L, int R) {
    if (L == R) return MX::unit();
    if (R == L + 1) return dat[0][L];
    int k = topbit(R - L - 1);
    return MX::op(dat[k][L], dat[k][R - (1 << k)]);
  }

  template <class F>
  int max_right(const F check, int L) {
    assert(0 <= L && L <= n && check(MX::unit()));
    if (L == n) return n;
    int ok = L, ng = n + 1;
    while (ok + 1 < ng) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(L, k));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }

  template <class F>
  int min_left(const F check, int R) {
    assert(0 <= R && R <= n && check(MX::unit()));
    if (R == 0) return 0;
    int ok = R, ng = -1;
    while (ng + 1 < ok) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(k, R));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }
};
#line 2 "ds/static_rmq.hpp"

// 構築 O(N), クエリ O(1)
template <typename Monoid>
struct Static_RMQ {
  using MX = Monoid;
  using X = typename MX::value_type;
  static constexpr int LOG = 4;
  int N, b_num;
  vc<X> A, pre, suf; // inclusive
  Sparse_Table<Monoid> ST;

  using u16 = unsigned short;
  vc<u16> dat;

  Static_RMQ() {}
  template <typename F>
  Static_RMQ(int n, F f) {
    build(n, f);
  }
  Static_RMQ(const vc<X>& v) { build(v); }

  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    N = m;
    b_num = N >> LOG;
    A.resize(N);
    FOR(i, N) A[i] = f(i);
    pre = A, suf = A;
    FOR(i, 1, N) {
      if (i & 15) pre[i] = MX::op(pre[i - 1], A[i]);
    }
    FOR_R(i, 1, N) {
      if (i & 15) suf[i - 1] = MX::op(A[i - 1], suf[i]);
    }
    ST.build(b_num, [&](int i) -> X { return suf[i << LOG]; });
    // 長さ 16 以下のクエリに対応するための前計算
    // [i,i+16) 内で i+j が [i,i+j] での最小値となる場合に j-th bit を立てる
    dat.resize(N);
    u32 stack = 0;
    FOR_R(i, N) {
      stack = (stack << 1) & 65535;
      while (stack) {
        int k = lowbit(stack);
        if (MX::op(A[i], A[i + k]) != A[i]) break;
        stack &= ~(u32(1) << k);
      }
      stack |= u32(1);
      dat[i] = stack;
    }
  }

  X prod(int L, int R) {
    assert(0 <= L && L <= R && R <= N);
    if (L == R) return MX::unit();
    if (R - L <= 16) {
      u32 d = dat[L] & ((u32(1) << (R - L)) - 1);
      return A[L + topbit(d)];
    }
    --R;
    int a = L >> LOG, b = R >> LOG;
    X x = ST.prod(a + 1, b);
    x = MX::op(suf[L], x);
    x = MX::op(x, pre[R]);
    return x;
  }
};

Back to top page