test/data_structure/segment_tree.range_min.test.cpp

View this file on GitHub
Last update: 2025-11-15 20:52:05+09:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Required by

test/utility/next_combination.test.cpp

Code

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

#include "../../data_structure/segment_tree.hpp"
#include "../../template/template.hpp"

ll op(ll a, ll b) { return min(a, b); }
ll e() { return INF<ll>; }

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<ll> A(N);
    rep (i, 0, N) {
        cin >> A[i];
    }

    SegmentTree<ll, op, e> seg(A);
    while (Q--) {
        int l, r;
        cin >> l >> r;

        cout << seg.prod(l, r) << LF;
    }

    return 0;
}

#line 1 "test/data_structure/segment_tree.range_min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#line 2 "data_structure/segment_tree.hpp"

#line 2 "template/template.hpp"

/**
 * @author ku_senjan
 * @title 提出用テンプレート
 * @see https://github.com/kogetsu0728/ku-library
 */

#line 2 "template/constant.hpp"

#line 2 "template/include.hpp"

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
using namespace std;
#line 2 "template/type_alias.hpp"

#line 4 "template/type_alias.hpp"

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

using ld = long double;

template <class T, bool REVERSE = false>
using heap = priority_queue<T, vector<T>, conditional_t<REVERSE, greater<T>, less<T>>>;
#line 5 "template/constant.hpp"

template <class T>
inline constexpr T INF = numeric_limits<T>::max() / 2;

inline constexpr array<int, 4> DY4 = {0, -1, 0, 1};
inline constexpr array<int, 4> DX4 = {1, 0, -1, 0};
inline constexpr array<int, 8> DY8 = {0, -1, -1, -1, 0, 1, 1, 1};
inline constexpr array<int, 8> DX8 = {1, 1, 0, -1, -1, -1, 0, 1};

inline constexpr char LF = '\n';
#line 2 "template/macro.hpp"

#line 5 "template/macro.hpp"

/**
 * @see https://trap.jp/post/1224/
 */

#ifdef LOCAL
inline constexpr bool IS_LOCAL = true;
#else
inline constexpr bool IS_LOCAL = false;
#endif

#define IF_LOCAL if constexpr (IS_LOCAL)

#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)

#define overload4(a, b, c, d, e, ...) e

#define rep1(i, a) for (ll i = 0; (i) < (ll)(a); ++(i))
#define rep2(i, a, b) for (ll i = (ll)(a); (i) < (ll)(b); ++(i))
#define rep3(i, a, b, c) for (ll i = (ll)(a); (i) < (ll)(b); (i) += (ll)(c))
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)

#define rrep1(i, a) for (ll i = (ll)(a); (i) >= 0; --(i))
#define rrep2(i, a, b) for (ll i = (ll)(a); (i) >= (ll)(b); --(i))
#define rrep3(i, a, b, c) for (ll i = (ll)(a); (i) >= (ll)(b); (i) -= (ll)(c))
#define rrep(...) overload4(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#line 13 "template/template.hpp"

#line 2 "utility/choose_min_max.hpp"

/**
 * @title Choose Minimum / Maximum
 */

template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }

    return false;
}

template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }

    return false;
}
#line 2 "utility/set_io.hpp"

#line 4 "utility/set_io.hpp"

void set_io(int d = 16) {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(d);

    return;
}
#line 4 "data_structure/segment_tree.hpp"

/**
 * @brief Segment Tree (セグメント木)
 */
template <class S, S (*op)(S, S), S (*e)()>
class SegmentTree {
  private:
    int n;
    vector<S> v;

    void update(int i) {
        v[i] = op(v[i << 1], v[(i << 1) | 1]);
        return;
    }

  public:
    SegmentTree() : SegmentTree(0) {}
    SegmentTree(int _n) : SegmentTree(vector<S>(_n, e())) {}
    SegmentTree(const vector<S>& _v) : n(int(_v.size())), v(_v.size() * 2, e()) {
        rep (i, 0, n) {
            v[n + i] = _v[i];
        }

        rrep (i, n - 1, 1) {
            update(i);
        }
    }

    S get(int i) const { return v[i + n]; }

    S prod(int l, int r) const {
        l += n;
        r += n;

        S v_l = e(), v_r = e();
        while (l < r) {
            if (l & 1) {
                v_l = op(v_l, v[l++]);
            }

            if (r & 1) {
                v_r = op(v[--r], v_r);
            }

            l >>= 1;
            r >>= 1;
        }

        return op(v_l, v_r);
    }

    void set(int i, S x) {
        i += n;
        v[i] = x;
        while (1 < i) {
            i >>= 1;
            update(i);
        }

        return;
    }
};
#line 5 "test/data_structure/segment_tree.range_min.test.cpp"

ll op(ll a, ll b) { return min(a, b); }
ll e() { return INF<ll>; }

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<ll> A(N);
    rep (i, 0, N) {
        cin >> A[i];
    }

    SegmentTree<ll, op, e> seg(A);
    while (Q--) {
        int l, r;
        cin >> l >> r;

        cout << seg.prod(l, r) << LF;
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	852 ms	15 MB
g++	max_random_01	AC	1004 ms	15 MB
g++	max_random_02	AC	865 ms	15 MB
g++	max_random_03	AC	881 ms	15 MB
g++	max_random_04	AC	835 ms	15 MB
g++	random_00	AC	695 ms	12 MB
g++	random_01	AC	760 ms	14 MB
g++	random_02	AC	555 ms	4 MB
g++	random_03	AC	167 ms	13 MB
g++	random_04	AC	220 ms	10 MB
g++	small_00	AC	6 ms	4 MB
g++	small_01	AC	6 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	5 ms	3 MB
g++	small_05	AC	5 ms	3 MB
g++	small_06	AC	5 ms	4 MB
g++	small_07	AC	5 ms	4 MB
g++	small_08	AC	5 ms	4 MB
g++	small_09	AC	5 ms	3 MB
g++	small_values_00	AC	756 ms	15 MB
g++	small_width_query_00	AC	818 ms	15 MB
g++	small_width_query_01	AC	810 ms	15 MB
g++	small_width_query_02	AC	881 ms	15 MB
g++	small_width_query_03	AC	894 ms	15 MB
g++	small_width_query_04	AC	843 ms	15 MB