YEZAELP

PROG-1147: Segment Tree

Jan 31st, 2021 (edited)
128
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None
  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