[AOJ] DSL_2_A Range Minimum Query (RMQ)
問題
方針
平方分割でこの問題を解いたことがありますが、セグメント木を使って解きました。
コード
#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; }
ディスカッション
コメント一覧
まだ、コメントがありません