# PROG-1147: Segment Tree

Jan 31st, 2021 (edited)
128
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. const int INF = 2e9;
6. int n;
7. int tree[2*(1<<19)]; // n = 262144 = 2^18 -> ประกาศ [2 * (n+1)]
8.
9. int update(int i, int l, int r, int pos, int val){
10.     if(l == r)
11.         return tree[i] = val;
12.     int mid = (l + r)/ 2;
13.     if(pos <= mid)
14.         return tree[i] = max(update(2*i, l, mid, pos, val), tree[2*i+1]);
15.     return tree[i] = max(tree[2*i], update(2*i+1, mid+1, r, pos, val));
16. }
17.
18. int query(int i, int l, int r, int s, int e){
19.     if(r < s or l > e)
20.         return -INF;
21.     if(s <= l and r <= e)
22.         return tree[i];
23.     int mid = (l + r)/ 2;
24.     return max(query(2*i, l, mid, s, e), query(2*i+1, mid+1, r, s, e)); // ระวัง ห้ามเก็บลง tree[i]
25. }
26.
27. int main(){
28.
29.     int q;
30.     scanf("%d%d", &n, &q);
31.
32.     while(q--){
33.         char a;
34.         scanf(" %c", &a);
35.         int x, y;
36.         scanf("%d%d", &x, &y);
37.         if(a == 'U')
38.             update(1, 1, n, x, y);
39.         else
40.             printf("%d\n", query(1, 1, n, x, y));
41.     }
42.
43.     return 0;
44. }
45.
RAW Paste Data Copied