Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using pi32 = pair<int, int>;
- const int maxN = 1e5 + 5;
- const int INF = 1e9 + 7;
- const int MOD = 998244353;
- int n;
- int a[maxN];
- void build(int id, int l, int r) {
- if (l == r) {
- t[id] = a[l];
- return;
- }
- int mid = (l + r) / 2;
- build(id*2, l, mid);
- build(id*2 + 1, mid + 1, r);
- t[id] = min(t[id*2], t[id*2 + 1]);
- }
- // Cập nhập: a[pos] = val
- void update(int id, int l, int r, int pos, int val) {
- if (pos < l || r < pos) return;
- if (l == r) {
- t[id] = val;
- return;
- }
- int mid = (l + r) / 2;
- update(id*2, l, mid, pos, val);
- update(id*2 + 1, mid+1, r, pos, val);
- t[id] = min(t[id*2], t[id*2 + 1]);
- }
- // Truy vấn: tìm min đoạn [u, v]
- int getMin(int id, int l, int r, int u, int v) {
- if (v < l || r < u) return INF;
- if (u <= l && r <= v) return t[id];
- int mid = (l + r) / 2;
- return min(getMin(id*2, l, mid, u, v), getMin(id*2 + 1, mid+1, r, u, v));
- }
- int main() {
- #ifdef LOCAL
- freopen("in1.txt", "r", stdin);
- #else
- freopen("Segment Tree - Min.inp", "r", stdin);
- freopen("Segment Tree - Min.out", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cin >> n;
- for (int i = 1; i <= n; ++i)
- cin >> a[i];
- build(1, 1, n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement