Advertisement
YEZAELP

C. Circular RMQ

Feb 23rd, 2021
224
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using lli = long long;
  6. const lli INF = 2e18;
  7. int n;
  8. lli ar[200010];
  9. lli tree[2 * (1<<19)];
  10. lli lazy[2 * (1<<19)];
  11.  
  12. lli build(int idx, int l, int r){
  13.     if(l == r) {
  14.         return tree[idx] = ar[l];
  15.     }
  16.     int mid = (l + r)/ 2;
  17.     return tree[idx] = min(build(2*idx, l, mid), build(2*idx+1, mid+1, r));
  18. }
  19.  
  20. void update(int idx, int l, int r, int s, int e, lli val){ // wrong update ทั้งหมดทั้งๆที่ไม่ได้อยู่ในช่วงเดียวกัน
  21.     if(lazy[idx] != 0){
  22.         tree[idx] += lazy[idx];
  23.         if(l != r){
  24.             lazy[2*idx] += lazy[idx];
  25.             lazy[2*idx + 1] += lazy[idx];
  26.         }
  27.         lazy[idx] = 0;
  28.     }
  29.     if(l > e or r < s) return;
  30.     if(s <= l and r <= e){
  31.         if(l != r){
  32.             lazy[2*idx] += val;
  33.             lazy[2*idx + 1] += val;
  34.         }
  35.         tree[idx] += val;
  36.         return;
  37.     }
  38.     int mid = (l + r)/ 2;
  39.     update(2*idx, l, mid, s, e, val);
  40.     update(2*idx + 1, mid + 1, r, s, e, val);
  41.     tree[idx] = min(tree[2*idx], tree[2*idx + 1]);
  42. }
  43.  
  44. lli query(int idx, int l, int r, int s, int e){
  45.     if(lazy[idx] != 0){
  46.         tree[idx] += lazy[idx];
  47.         if(l != r){
  48.             lazy[2*idx] += lazy[idx];
  49.             lazy[2*idx + 1] += lazy[idx];
  50.         }
  51.         lazy[idx] = 0;
  52.     }
  53.     if(l > e or r < s) return INF;
  54.     if(s <= l and r <= e) return tree[idx];
  55.     int mid = (l + r)/ 2;
  56.     return min(query(2*idx, l, mid, s, e), query(2*idx + 1, mid + 1, r, s, e));
  57. }
  58.  
  59. int main(){
  60.  
  61.     scanf("%d", &n);
  62.     for(int i=0;i<n;i++){
  63.         scanf("%lld", &ar[i]);
  64.     }
  65.  
  66.     build(1, 0, n-1);
  67.  
  68.     int m;
  69.     scanf("%d", &m);
  70.     for(int i=1;i<=m;i++){
  71.         int l, r;
  72.         scanf("%d%d", &l, &r);
  73.         if(cin.peek() != '\n'){
  74.             lli a;
  75.             scanf("%lld", &a);
  76.             if(l <= r) update(1, 0, n-1, l, r, a);
  77.             else{
  78.                 update(1, 0, n-1, 0, r, a);
  79.                 update(1, 0, n-1, l, n-1, a);
  80.             }
  81.         }
  82.         else {
  83.            if(l <= r) printf("%lld\n", query(1, 0, n-1, l, r));
  84.            else printf("%lld\n", min(query(1, 0, n-1, 0, r), query(1, 0, n-1, l, n-1)));
  85.         }
  86.     }
  87.  
  88.     return 0;
  89. }
  90.  
Advertisement
RAW Paste Data Copied
Advertisement