Advertisement
YEZAELP

o57_oct_c2_fallingblocks

Jan 6th, 2022
591
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. const int inf = 2e9;
  5. const int N = 1e5;
  6. struct Node{
  7.     int hl, hr, up, down;
  8. };
  9. Node tree[(1 << 18)];
  10. int lazy[(1 << 18)];
  11.  
  12. Node Combine(Node L, Node R){
  13.     Node cur;
  14.     cur.hl = L.hl;
  15.     cur.hr = R.hr;
  16.     cur.up = L.up + R.up;
  17.     cur.down = L.down + R.down;
  18.     int l = L.hr, r = R.hl;
  19.     if(l < r) cur.up ++;
  20.     else if(l > r) cur.down ++;
  21.     return cur;
  22. }
  23.  
  24. void Lazy(int idx, int l, int r){
  25.     if(lazy[idx] == 0) return;
  26.     if(l != r){
  27.         lazy[2 * idx] += lazy[idx];
  28.         lazy[2 * idx + 1] += lazy[idx];
  29.     }
  30.     tree[idx].hl += lazy[idx];
  31.     tree[idx].hr += lazy[idx];
  32.     lazy[idx] = 0;
  33. }
  34.  
  35. void Update(int idx, int l, int r, int s, int e){
  36.     Lazy(idx, l, r);
  37.     if(l > e or r < s) return;
  38.     if(s <= l and r <= e){
  39.         if(l != r){
  40.             lazy[2 * idx] ++;
  41.             lazy[2 * idx + 1] ++;
  42.         }
  43.         tree[idx].hl ++;
  44.         tree[idx].hr ++;
  45.         return;
  46.     }
  47.     int mid = (l + r) / 2;
  48.     Update(2 * idx, l, mid, s, e);
  49.     Update(2 * idx + 1, mid + 1, r, s, e);
  50.     tree[idx] = Combine(tree[2 * idx], tree[2 * idx + 1]);
  51. }
  52.  
  53. Node Query(int idx, int l, int r, int s, int e){
  54.     Lazy(idx, l, r);
  55.     if(l > e or r < s) return {inf, inf, inf, inf};
  56.     if(s <= l and r <= e)
  57.         return tree[idx];
  58.     int mid = (l + r) / 2;
  59.     if(mid < s) return Query(2 * idx + 1, mid + 1, r, s, e);
  60.     else if(e < mid + 1) return Query(2 * idx, l, mid, s, e);
  61.     Node L = Query(2 * idx, l, mid, s, e);
  62.     Node R = Query(2 * idx + 1, mid + 1, r, s, e);
  63.     return Combine(L, R);
  64. }
  65.  
  66. int main(){
  67.  
  68.     int n, m;
  69.     scanf("%d %d", &n, &m);
  70.  
  71.     for(int i=1;i<=m;i++){
  72.         int opr, x, y;
  73.         scanf("%d %d %d", &opr, &x, &y);
  74.         if(opr == 1)
  75.             Update(1, 1, n, x, y);
  76.         else if(opr == 2){
  77.             Node Q = Query(1, 1, n, x, y);
  78.             printf("%d %d\n", Q.hl, Q.hr);
  79.         }
  80.         else {
  81.             Node Q = Query(1, 1, n, x, y);
  82.             printf("%d %d %d %d\n", Q.hl, Q.hr, Q.up, Q.down);
  83.         }
  84.     }
  85.  
  86.     return 0;
  87. }
Advertisement
RAW Paste Data Copied
Advertisement