verify/yosupo/yosupo_staticrmq.test.cpp

• View this file on GitHub
• Last update: 2024-07-23 19:50:25+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• data_structure/segment_tree.hpp

Code

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

#include <bits/stdc++.h>
using namespace std;

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

constexpr int INF = 1e9 + 10;

using S = int;
inline S op(S l, S r) { return min(l, r); }
inline S e() { return INF; }

int main() {
    int N, Q;
    cin >> N >> Q;

    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

    SegmentTree<S, op, e> seg(A);

    while(Q--) {
        int l, r;
        cin >> l >> r;
        cout << seg.prod(l, r) << endl;
    }


    return 0;
}

#line 1 "verify/yosupo/yosupo_staticrmq.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <bits/stdc++.h>
using namespace std;

#line 1 "data_structure/segment_tree.hpp"
template<class S, S (*op)(S, S), S (*e)()>
struct SegmentTree{
    int n;
    vector<S> data;

    SegmentTree(int sz=0) : n(1) {
        while(n < sz) n *= 2;
        data.resize(2 * n, e());
    }

    SegmentTree(const vector<S> &V) : n(1) {
        int sz = V.size();
        while(n < sz) n *= 2;
        data.resize(2 * n, e());
        for(int i = 0; i < sz; i++) data[i+n] = V[i];
        for(int i = n - 1; i >= 1; i--) data[i] = op(data[i<<1], data[i<<1|1]);
    }

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

    S prod(int l, int r) {
        l += n; r += n;
        S vl = e(), vr = e();
        while(l < r) {
            if(l & 1) vl = op(vl, data[l++]);
            if(r & 1) vr = op(data[--r], vr);
            l >>= 1; r >>= 1;
        }
        return op(vl, vr);
    }

    S all_prod() { return data[1]; }

    S get(int i) { return data[i + n]; }
};
#line 7 "verify/yosupo/yosupo_staticrmq.test.cpp"

constexpr int INF = 1e9 + 10;

using S = int;
inline S op(S l, S r) { return min(l, r); }
inline S e() { return INF; }

int main() {
    int N, Q;
    cin >> N >> Q;

    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

    SegmentTree<S, op, e> seg(A);

    while(Q--) {
        int l, r;
        cin >> l >> r;
        cout << seg.prod(l, r) << endl;
    }


    return 0;
}

Back to top page