Alex_tz307

Segment Tree Beats(without set and gcd)

May 8th, 2021
883
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. using int64 = long long;
  5.  
  6. void fastIO() {
  7.   ios_base::sync_with_stdio(false);
  8.   cin.tie(nullptr);
  9.   cout.tie(nullptr);
  10. }
  11.  
  12. const int64 INF = 1e18L;
  13.  
  14. struct node {
  15.   int64 max1, max2, min1, min2, sum, lazy_add;
  16.   int cnt_max, cnt_min;
  17. };
  18.  
  19. struct SegTree {
  20.   int Size;
  21.   vector<node> tree;
  22.  
  23.   SegTree(int N) {
  24.     Size = 1;
  25.     while (Size < N)
  26.       Size <<= 1;
  27.     tree.resize(Size << 1);
  28.   }
  29.  
  30.   node join(const node &a, const node &b) {
  31.     node x;
  32.     x.sum = a.sum + b.sum;
  33.     x.lazy_add = 0;
  34.     if (a.max1 > b.max1) {
  35.       x.max1 = a.max1;
  36.       x.cnt_max = a.cnt_max;
  37.       x.max2 = max(a.max2, b.max1);
  38.     } else {
  39.       if (a.max1 < b.max1) {
  40.         x.max1 = b.max1;
  41.         x.cnt_max = b.cnt_max;
  42.         x.max2 = max(a.max1, b.max2);
  43.       } else {
  44.         x.max1 = a.max1;
  45.         x.cnt_max = a.cnt_max + b.cnt_max;
  46.         x.max2 = max(a.max2, b.max2);
  47.       }
  48.     }
  49.     if (a.min1 < b.min1) {
  50.       x.min1 = a.min1;
  51.       x.cnt_min = a.cnt_min;
  52.       x.min2 = min(a.min2, b.min1);
  53.     } else {
  54.       if (a.min1 > b.min1) {
  55.         x.min1 = b.min1;
  56.         x.cnt_min = b.cnt_min;
  57.         x.min2 = min(a.min1, b.min2);
  58.       } else {
  59.         x.min1 = a.min1;
  60.         x.cnt_min = a.cnt_min + b.cnt_min;
  61.         x.min2 = min(a.min2, b.min2);
  62.       }
  63.     }
  64.     return x;
  65.   }
  66.  
  67.   void build(int x, int lx, int rx) {
  68.     if (lx == rx) {
  69.       int64 val;
  70.       cin >> val;
  71.       tree[x].max1 = tree[x].min1 = tree[x].sum = val;
  72.       tree[x].max2 = -INF;
  73.       tree[x].min2 = INF;
  74.       tree[x].cnt_max = tree[x].cnt_min = 1;
  75.       tree[x].lazy_add = 0;
  76.       return;
  77.     }
  78.     int mid = (lx + rx) >> 1;
  79.     build(x << 1, lx, mid);
  80.     build(x << 1 | 1, mid + 1, rx);
  81.     tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  82.   }
  83.  
  84.   void update_node_max(int x, int64 val) {
  85.     tree[x].sum += (val - tree[x].max1) * tree[x].cnt_max;
  86.     if (tree[x].max1 == tree[x].min1)
  87.       tree[x].max1 = tree[x].min1 = val;
  88.     else {
  89.       if (tree[x].max1 == tree[x].min2)
  90.         tree[x].max1 = tree[x].min2 = val;
  91.       else tree[x].max1 = val;
  92.     }
  93.   }
  94.  
  95.   void update_node_min(int x, int64 val) {
  96.     tree[x].sum += (val - tree[x].min1) * tree[x].cnt_min;
  97.     if (tree[x].min1 == tree[x].max1)
  98.       tree[x].min1 = tree[x].max1 = val;
  99.     else {
  100.       if (tree[x].min1 == tree[x].max2)
  101.         tree[x].min1 = tree[x].max2 = val;
  102.       else tree[x].min1 = val;
  103.     }
  104.   }
  105.  
  106.   void update_node_add(int x, int n, int64 val) {
  107.     tree[x].max1 += val;
  108.     if (tree[x].max2 != -INF)
  109.       tree[x].max2 += val;
  110.     tree[x].min1 += val;
  111.     if (tree[x].min2 != INF)
  112.       tree[x].min2 += val;
  113.     tree[x].sum += val * n;
  114.     tree[x].lazy_add += val;
  115.   }
  116.  
  117.   void push(int x, int lx, int rx) {
  118.     if (lx == rx)
  119.       return;
  120.     int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
  121.     int l1 = mid - lx + 1, l2 = rx - mid;
  122.     if (tree[x].lazy_add != 0) {
  123.       update_node_add(lSon, l1, tree[x].lazy_add);
  124.       update_node_add(rSon, l2, tree[x].lazy_add);
  125.       tree[x].lazy_add = 0;
  126.     }
  127.     for (int i = 0; i < 2; ++i) {
  128.       int son = x << 1 | i;
  129.       if (tree[x].max1 < tree[son].max1)
  130.         update_node_max(son, tree[x].max1);
  131.       if (tree[x].min1 > tree[son].min1)
  132.         update_node_min(son, tree[x].min1);
  133.     }
  134.   }
  135.  
  136.   void update_min(int x, int lx, int rx, int st, int dr, int64 val) {
  137.     if (val >= tree[x].max1)
  138.       return;
  139.     if (st <= lx && rx <= dr && val > tree[x].max2) {
  140.       update_node_max(x, val);
  141.       return;
  142.     }
  143.     push(x, lx, rx);
  144.     int mid = (lx + rx) >> 1;
  145.     if (st <= mid)
  146.       update_min(x << 1, lx, mid, st, dr, val);
  147.     if (mid < dr)
  148.       update_min(x << 1 | 1, mid + 1, rx, st, dr, val);
  149.     tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  150.   }
  151.  
  152.   void update_max(int x, int lx, int rx, int st, int dr, int64 val) {
  153.     if (val <= tree[x].min1)
  154.       return;
  155.     if (st <= lx && rx <= dr && val < tree[x].min2) {
  156.       update_node_min(x, val);
  157.       return;
  158.     }
  159.     push(x, lx, rx);
  160.     int mid = (lx + rx) >> 1;
  161.     if (st <= mid)
  162.       update_max(x << 1, lx, mid, st, dr, val);
  163.     if (mid < dr)
  164.       update_max(x << 1 | 1, mid + 1, rx, st, dr, val);
  165.     tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  166.   }
  167.  
  168.   void update_add(int x, int lx, int rx, int st, int dr, int64 val) {
  169.     if (st <= lx && rx <= dr) {
  170.       update_node_add(x, rx - lx + 1, val);
  171.       return;
  172.     }
  173.     push(x, lx, rx);
  174.     int mid = (lx + rx) >> 1;
  175.     if (st <= mid)
  176.       update_add(x << 1, lx, mid, st, dr, val);
  177.     if (mid < dr)
  178.       update_add(x << 1 | 1, mid + 1, rx, st, dr, val);
  179.     tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  180.   }
  181.  
  182.   int64 query_sum(int x, int lx, int rx, int st, int dr) {
  183.     if (st <= lx && rx <= dr)
  184.       return tree[x].sum;
  185.     push(x, lx, rx);
  186.     int mid = (lx + rx) >> 1;
  187.     int64 ans = 0;
  188.     if (st <= mid)
  189.       ans += query_sum(x << 1, lx, mid, st, dr);
  190.     if (mid < dr)
  191.       ans += query_sum(x << 1 | 1, mid + 1, rx, st, dr);
  192.     return ans;
  193.   }
  194. };
  195.  
  196. void solve() {
  197.   int N, Q;
  198.   cin >> N >> Q;
  199.   SegTree tree(N);
  200.   tree.build(1, 1, N);
  201.   for (int q = 0; q < Q; ++q) {
  202.     int op, l, r;
  203.     int64 x;
  204.     cin >> op >> l >> r;
  205.     ++l;
  206.     if (op < 3)
  207.       cin >> x;
  208.     if (op == 0)
  209.       tree.update_min(1, 1, N, l, r, x);
  210.     else {
  211.       if (op == 1)
  212.         tree.update_max(1, 1, N, l, r, x);
  213.       else {
  214.         if (op == 2)
  215.           tree.update_add(1, 1, N, l, r, x);
  216.         else cout << tree.query_sum(1, 1, N, l, r) << '\n';
  217.       }
  218.     }
  219.   }
  220. }
  221.  
  222. int main() {
  223.   fastIO();
  224.   solve();
  225.   return 0;
  226. }
  227.  
RAW Paste Data