ds/rmq/suffix_min.hpp

• View this file on GitHub
• Last update: 2025-10-13 18:56:57+09:00
• Include: #include "ds/rmq/suffix_min.hpp"

Depends on

• ds/unionfind/unionfind.hpp

Code

#include "ds/unionfind/unionfind.hpp"

// 末尾代入
// find min of (a[i],...,a[p-1])
template <typename T>
struct Suffix_Min {
  // 内部的な処理としては a ではなく ANS を管理する.
  // ANS[0],...,ANS[p] に chmin(x) が来ると思う
  int N, p;
  UnionFind uf;
  vc<T> ANS;
  vc<pair<T, int>> st;  // (value, uf root)
  Suffix_Min(int N) : N(N), p(0), uf(N + 1), ANS(N + 1, infty<T>) {
    st.reserve(N);
  }

  void reset() {
    uf.reset();
    fill(all(ANS), infty<T>);
    st.clear();
    p = 0;
  }

  void set(int i, T x) {
    assert(p == i);
    while (!st.empty() && st.back().fi >= x) {
      uf.merge(p, st.back().se);
      st.pop_back();
    }
    int r = uf[p++];
    ANS[r] = x, st.eb(x, r);
  }
  T query(int i) {
    assert(i <= p);
    return ANS[uf[i]];
  }
};

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

struct UnionFind {
  int n, n_comp;
  vc<int> dat; // par or (-size)
  UnionFind(int n = 0) { build(n); }

  void build(int m) {
    n = m, n_comp = m;
    dat.assign(n, -1);
  }

  void reset() { build(n); }

  int operator[](int x) {
    while (dat[x] >= 0) {
      int pp = dat[dat[x]];
      if (pp < 0) { return dat[x]; }
      x = dat[x] = pp;
    }
    return x;
  }

  ll size(int x) {
    x = (*this)[x];
    return -dat[x];
  }

  bool merge(int x, int y) {
    x = (*this)[x], y = (*this)[y];
    if (x == y) return false;
    if (-dat[x] < -dat[y]) swap(x, y);
    dat[x] += dat[y], dat[y] = x, n_comp--;
    return true;
  }

  vc<int> get_all() {
    vc<int> A(n);
    FOR(i, n) A[i] = (*this)[i];
    return A;
  }
};
#line 2 "ds/rmq/suffix_min.hpp"

// 末尾代入
// find min of (a[i],...,a[p-1])
template <typename T>
struct Suffix_Min {
  // 内部的な処理としては a ではなく ANS を管理する.
  // ANS[0],...,ANS[p] に chmin(x) が来ると思う
  int N, p;
  UnionFind uf;
  vc<T> ANS;
  vc<pair<T, int>> st;  // (value, uf root)
  Suffix_Min(int N) : N(N), p(0), uf(N + 1), ANS(N + 1, infty<T>) {
    st.reserve(N);
  }

  void reset() {
    uf.reset();
    fill(all(ANS), infty<T>);
    st.clear();
    p = 0;
  }

  void set(int i, T x) {
    assert(p == i);
    while (!st.empty() && st.back().fi >= x) {
      uf.merge(p, st.back().se);
      st.pop_back();
    }
    int r = uf[p++];
    ANS[r] = x, st.eb(x, r);
  }
  T query(int i) {
    assert(i <= p);
    return ANS[uf[i]];
  }
};

Back to top page