[AOJ] DSL_2_A Range Minimum Query (RMQ)

2020年12月17日

問題

方針

平方分割でこの問題を解いたことがありますが、セグメント木を使って解きました。

コード

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

class SegmentTree {
private:
    int n;
    vector<ll> node;
    ll INF = (1ll << 31) - 1;
public:
    SegmentTree(int N) {
        n = 1;
        while (n < N) n *= 2;
        node.resize(2 * n - 1, INF);
    }

    void update(int i, ll x) {
        i += (n - 1);
        node[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            node[i] = min(node[2 * i + 1], node[2 * i + 2]);
        }
    }

    ll query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return INF;
        if (a <= l && r <= b) return node[k];
        ll vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        ll vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);
    }

};


int main() {
    int n, q;
    cin >> n >> q;
    ll com, x, y;
    SegmentTree st(n);
    int N = 1;
    while (N < n) N *= 2;
    for (int i = 0; i < q; i++) {
        cin >> com >> x >> y;
        if (com == 0) {
            st.update(x, y);
        } else {
            cout << st.query(x, y + 1, 0, 0, N) << "\n";
        }
    }
    return 0;
}