Plus Minus One RMQ
(datastructure/plus_minus_one_rmq.hpp)

View this file on GitHub
Last update: 2026-10-26 01:30:50+09:00
Include: #include "datastructure/plus_minus_one_rmq.hpp"

概要

隣接要素の差が $\pm 1$ の配列の区間最小値の位置を求める。

使い方

plus_minus_one_rmq(a): 配列 a で構築する。
prod(l, r): a[l], ..., a[r - 1] の最小値の添字を返す。複数あれば最小の添字。

制約

$\lvert a_i - a_{i+1} \rvert = 1$
$0 \le l < r \le n$

計算量

構築: $\mathcal{O}(N)$
prod: $\mathcal{O}(1)$

Depends on

Required by

最小共通祖先(LCA) (graph/lowest_common_ancestor.hpp)

Verified with

Code

#pragma once
#include <algorithm>
#include <bit>
#include <cassert>
#include <vector>

#include "datastructure/sparse_table.hpp"
#include "algebra/monoid_argmin.hpp"
struct plus_minus_one_rmq {
public:
    plus_minus_one_rmq() : _n(0), s(1), B(0) {
    }
    explicit plus_minus_one_rmq(const std::vector<int>& a) : _n(int(a.size())), v(a) {
        s = std::max(1, (std::bit_width((unsigned)_n) - 1) / 2);
        B = (_n + s - 1) / s;
        std::vector<monoid_argmin<int>::S> blocks(B);
        pattern.resize(B);
        for (int i = 0; i < _n; i += s) {
            int min_j = i;
            int bit = 0;
            int end = std::min(_n, i + s);
            for (int j = i; j < end; j++) {
                if (v[j] < v[min_j]) min_j = j;
                if (j + 1 < end && v[j] < v[j + 1]) bit |= 1 << (j - i);
            }
            blocks[i / s] = {v[min_j], min_j};
            pattern[i / s] = bit;
        }
        table = sparse_table<monoid_argmin<int>>(blocks);
        lookup.resize(1 << (s - 1));
        for (int bit = 0; bit < (1 << (s - 1)); bit++) {
            lookup[bit].resize(s + 1);
            for (int l = 0; l <= s; l++) {
                lookup[bit][l].assign(s + 1, INF);
                int min_sum = 0, min_i = l, sum = 0;
                for (int r = l + 1; r <= s; r++) {
                    lookup[bit][l][r] = min_i;
                    sum += bit >> (r - 1) & 1 ? 1 : -1;
                    if (sum < min_sum) {
                        min_sum = sum;
                        min_i = r;
                    }
                }
            }
        }
    }
    int prod(int l, int r) const {
        assert(0 <= l && l < r && r <= _n);
        int m1 = (l + s - 1) / s, m2 = r / s;
        int l1 = s * m1, r1 = s * m2;
        if (m2 < m1) return lookup[pattern[m2]][l - r1][r - r1] + r1;
        int ret = INF;
        if (m1 > 0) ret = argmin(ret, lookup[pattern[m1 - 1]][s - (l1 - l)][s] + l1 - s);
        if (m1 < m2) ret = argmin(ret, table.prod(m1, m2).id);
        if (m2 < B) ret = argmin(ret, lookup[pattern[m2]][0][r - r1] + r1);
        return ret;
    }

private:
    static constexpr int INF = 1 << 30;
    int _n, s, B;
    std::vector<int> v, pattern;
    sparse_table<monoid_argmin<int>> table;
    std::vector<std::vector<std::vector<int>>> lookup;
    int argmin(int i, int j) const {
        if (i >= INF) return j;
        if (j >= INF) return i;
        if (v[i] != v[j]) return v[i] < v[j] ? i : j;
        return std::min(i, j);
    }
};

#line 2 "datastructure/plus_minus_one_rmq.hpp"
#include <algorithm>
#include <bit>
#include <cassert>
#include <vector>

#line 6 "datastructure/sparse_table.hpp"

#line 2 "algebra/concept.hpp"
#include <concepts>
template <class M>
concept semigroup = requires(typename M::S a, typename M::S b) {
    { M::op(a, b) } -> std::same_as<typename M::S>;
};
template <class M>
concept monoid = semigroup<M> && requires {
    { M::e() } -> std::same_as<typename M::S>;
};
template <class G>
concept group = monoid<G> && requires(typename G::S a) {
    { G::inv(a) } -> std::same_as<typename G::S>;
};
template <class A>
concept action = requires(typename A::F f, typename A::F g) {
    { A::composition(f, g) } -> std::same_as<typename A::F>;
    { A::id() } -> std::same_as<typename A::F>;
    { A::composition_commutative } -> std::convertible_to<bool>;
};
template <class A>
concept acted_monoid = monoid<A> && action<A> && requires(typename A::S x, typename A::F f) {
    { A::mapping(f, x) } -> std::same_as<typename A::S>;
};
template <class R>
concept semiring = requires(typename R::S a, typename R::S b) {
    { R::add(a, b) } -> std::same_as<typename R::S>;
    { R::zero() } -> std::same_as<typename R::S>;
    { R::mul(a, b) } -> std::same_as<typename R::S>;
    { R::one() } -> std::same_as<typename R::S>;
};
#line 8 "datastructure/sparse_table.hpp"
template <semigroup M> struct sparse_table {
    using S = typename M::S;
    sparse_table() : _n(0) {
    }
    explicit sparse_table(const std::vector<S>& a) : _n(int(a.size())) {
        int log = std::max(1, std::bit_width((unsigned)_n));
        t.resize(log);
        t[0] = a;
        for (int k = 1; k < log; k++) {
            t[k].resize(_n - (1 << k) + 1);
            for (int i = 0; i + (1 << k) <= _n; i++) {
                t[k][i] = M::op(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    S prod(int l, int r) const {
        assert(0 <= l && l < r && r <= _n);
        int k = std::bit_width((unsigned)(r - l)) - 1;
        return M::op(t[k][l], t[k][r - (1 << k)]);
    }

private:
    int _n;
    std::vector<std::vector<S>> t;
};
#line 2 "algebra/monoid_argmin.hpp"
#include <limits>
template <class T>
struct monoid_argmin {
    struct S {
        T val;
        int id;
    };
    static S op(S a, S b) {
        if (a.val != b.val) return a.val < b.val ? a : b;
        return a.id < b.id ? a : b;
    }
    static S e() {
        return {std::numeric_limits<T>::max(), -1};
    }
};
#line 9 "datastructure/plus_minus_one_rmq.hpp"
struct plus_minus_one_rmq {
public:
    plus_minus_one_rmq() : _n(0), s(1), B(0) {
    }
    explicit plus_minus_one_rmq(const std::vector<int>& a) : _n(int(a.size())), v(a) {
        s = std::max(1, (std::bit_width((unsigned)_n) - 1) / 2);
        B = (_n + s - 1) / s;
        std::vector<monoid_argmin<int>::S> blocks(B);
        pattern.resize(B);
        for (int i = 0; i < _n; i += s) {
            int min_j = i;
            int bit = 0;
            int end = std::min(_n, i + s);
            for (int j = i; j < end; j++) {
                if (v[j] < v[min_j]) min_j = j;
                if (j + 1 < end && v[j] < v[j + 1]) bit |= 1 << (j - i);
            }
            blocks[i / s] = {v[min_j], min_j};
            pattern[i / s] = bit;
        }
        table = sparse_table<monoid_argmin<int>>(blocks);
        lookup.resize(1 << (s - 1));
        for (int bit = 0; bit < (1 << (s - 1)); bit++) {
            lookup[bit].resize(s + 1);
            for (int l = 0; l <= s; l++) {
                lookup[bit][l].assign(s + 1, INF);
                int min_sum = 0, min_i = l, sum = 0;
                for (int r = l + 1; r <= s; r++) {
                    lookup[bit][l][r] = min_i;
                    sum += bit >> (r - 1) & 1 ? 1 : -1;
                    if (sum < min_sum) {
                        min_sum = sum;
                        min_i = r;
                    }
                }
            }
        }
    }
    int prod(int l, int r) const {
        assert(0 <= l && l < r && r <= _n);
        int m1 = (l + s - 1) / s, m2 = r / s;
        int l1 = s * m1, r1 = s * m2;
        if (m2 < m1) return lookup[pattern[m2]][l - r1][r - r1] + r1;
        int ret = INF;
        if (m1 > 0) ret = argmin(ret, lookup[pattern[m1 - 1]][s - (l1 - l)][s] + l1 - s);
        if (m1 < m2) ret = argmin(ret, table.prod(m1, m2).id);
        if (m2 < B) ret = argmin(ret, lookup[pattern[m2]][0][r - r1] + r1);
        return ret;
    }

private:
    static constexpr int INF = 1 << 30;
    int _n, s, B;
    std::vector<int> v, pattern;
    sparse_table<monoid_argmin<int>> table;
    std::vector<std::vector<std::vector<int>>> lookup;
    int argmin(int i, int j) const {
        if (i >= INF) return j;
        if (j >= INF) return i;
        if (v[i] != v[j]) return v[i] < v[j] ? i : j;
        return std::min(i, j);
    }
};

Plus Minus One RMQ (datastructure/plus_minus_one_rmq.hpp)

概要

使い方

制約

計算量

Depends on

Required by

Verified with

Code

Plus Minus One RMQ
(datastructure/plus_minus_one_rmq.hpp)