Alex_tz307

Segment Tree Beats

Apr 22nd, 2021 (edited)
406
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define ABS(x) ((x) >= 0 ? (x) : -(x))
  3.  
  4. using namespace std;
  5. using int64 = long long;
  6.  
  7. void fastIO() {
  8.   ios_base::sync_with_stdio(false);
  9.   cin.tie(nullptr);
  10.   cout.tie(nullptr);
  11. }
  12.  
  13. void max_self(int64 &a, int64 b) {
  14.   a = max(a, b);
  15. }
  16.  
  17. void min_self(int64 &a, int64 b) {
  18.   a = min(a, b);
  19. }
  20.  
  21. int64 gcd(int64 x, int64 y) {
  22.   x = ABS(x), y = ABS(y);
  23.   while (y) {
  24.     int64 r = x % y;
  25.     x = y;
  26.     y = r;
  27.   }
  28.   return x;
  29. }
  30.  
  31. const int64 INF = 1e18L;
  32.  
  33. struct node {
  34.   int64 max1, max2, min1, min2, sum, diff_gcd, lazy_set, lazy_add;
  35.   int cnt_max, cnt_min;
  36. };
  37.  
  38. struct SegTree {
  39.   int Size;
  40.   vector<node> tree;
  41.  
  42.   SegTree(int N) {
  43.     Size = 1;
  44.     while (Size < N)
  45.       Size <<= 1;
  46.     tree.resize(Size << 1);
  47.   }
  48.  
  49.   node join(const node &a, const node &b) {
  50.     node x;
  51.     x.sum = a.sum + b.sum;
  52.     x.lazy_add = 0;
  53.     x.lazy_set = INF;
  54.     if (a.max1 > b.max1) {
  55.       x.max1 = a.max1;
  56.       x.cnt_max = a.cnt_max;
  57.       x.max2 = max(a.max2, b.max1);
  58.     } else {
  59.       if (a.max1 < b.max1) {
  60.         x.max1 = b.max1;
  61.         x.cnt_max = b.cnt_max;
  62.         x.max2 = max(a.max1, b.max2);
  63.       } else {
  64.         x.max1 = a.max1;
  65.         x.cnt_max = a.cnt_max + b.cnt_max;
  66.         x.max2 = max(a.max2, b.max2);
  67.       }
  68.     }
  69.     if (a.min1 < b.min1) {
  70.       x.min1 = a.min1;
  71.       x.cnt_min = a.cnt_min;
  72.       x.min2 = min(a.min2, b.min1);
  73.     } else {
  74.       if (a.min1 > b.min1) {
  75.         x.min1 = b.min1;
  76.         x.cnt_min = b.cnt_min;
  77.         x.min2 = min(a.min1, b.min2);
  78.       } else {
  79.         x.min1 = a.min1;
  80.         x.cnt_min = a.cnt_min + b.cnt_min;
  81.         x.min2 = min(a.min2, b.min2);
  82.       }
  83.     }
  84.     x.diff_gcd = gcd(a.diff_gcd, b.diff_gcd);
  85.     int64 any = -1;
  86.     for (int64 any_left : {a.min2, a.max2}) {
  87.       if (ABS(any_left) == INF || any_left == x.min1 || any_left == x.max1)
  88.         continue;
  89.       any = any_left;
  90.       for (int64 any_right : {b.min2, b.max2}) {
  91.         if (ABS(any_right) == INF || any_right == x.min1 || any_right == x.max1)
  92.           continue;
  93.         x.diff_gcd = gcd(x.diff_gcd, any_left - any_right);
  94.       }
  95.     }
  96.     for (int64 any_right : {b.min2, b.max2}) {
  97.       if (ABS(any_right) == INF || any_right == x.min1 || any_right == x.max1)
  98.         continue;
  99.       any = any_right;
  100.     }
  101.     for (int64 val : {a.min1, a.max1, b.min1, b.max1}) {
  102.       if (val == x.min1 || val == x.max1)
  103.         continue;
  104.       if (any != -1)
  105.         x.diff_gcd = gcd(x.diff_gcd, any - val);
  106.       else any = val;
  107.     }
  108.     return x;
  109.   }
  110.  
  111.   void build(int x, int lx, int rx) {
  112.     if (lx == rx) {
  113.       int64 val;
  114.       cin >> val;
  115.       tree[x].max1 = tree[x].min1 = tree[x].sum = val;
  116.       tree[x].max2 = -INF;
  117.       tree[x].min2 = INF;
  118.       tree[x].cnt_max = tree[x].cnt_min = 1;
  119.       tree[x].diff_gcd = tree[x].lazy_add = 0;
  120.       tree[x].lazy_set = INF;
  121.       return;
  122.     }
  123.     int mid = (lx + rx) >> 1;
  124.     build(x << 1, lx, mid);
  125.     build(x << 1 | 1, mid + 1, rx);
  126.     tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  127.   }
  128.  
  129.   void push_set(int x, int n, int64 val) {
  130.     tree[x].max1 = tree[x].min1 = tree[x].lazy_set = val;
  131.     tree[x].cnt_max = tree[x].cnt_min = n;
  132.     tree[x].max2 = -INF;
  133.     tree[x].min2 = INF;
  134.     tree[x].sum = val * n;
  135.     tree[x].diff_gcd = tree[x].lazy_add = 0;
  136.   }
  137.  
  138.   void push_min_equal(int x, int n, int64 val) {
  139.     if (val <= tree[x].min1)
  140.       push_set(x, n, val);
  141.     else if (val < tree[x].max1) {
  142.       if (tree[x].min2 == tree[x].max1)
  143.         tree[x].min2 = val;
  144.       tree[x].sum -= (tree[x].max1 - val) * tree[x].cnt_max;
  145.       tree[x].max1 = val;
  146.     }
  147.   }
  148.  
  149.   void push_max_equal(int x, int n, int64 val) {
  150.     if (tree[x].max1 <= val)
  151.       push_set(x, n, val);
  152.     else if (val > tree[x].min1) {
  153.       if (tree[x].max2 == tree[x].min1)
  154.         tree[x].max2 = val;
  155.       tree[x].sum += (val - tree[x].min1) * tree[x].cnt_min;
  156.       tree[x].min1 = val;
  157.     }
  158.   }
  159.  
  160.   void push_add(int x, int n, int64 val) {
  161.     tree[x].max1 += val;
  162.     if (tree[x].max2 != -INF)
  163.       tree[x].max2 += val;
  164.     tree[x].min1 += val;
  165.     if (tree[x].min2 != INF)
  166.       tree[x].min2 += val;
  167.     tree[x].sum += val * n;
  168.     if (tree[x].lazy_set != INF)
  169.       tree[x].lazy_set += val;
  170.     else tree[x].lazy_add += val;
  171.   }
  172.  
  173.   void push(int x, int lx, int rx) {
  174.     if (lx == rx)
  175.       return;
  176.     int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
  177.     int l1 = mid - lx + 1, l2 = rx - mid;
  178.     if (tree[x].lazy_set != INF) {
  179.       push_set(lSon, l1, tree[x].lazy_set);
  180.       push_set(rSon, l2, tree[x].lazy_set);
  181.       tree[x].lazy_set = INF;
  182.       return;
  183.     }
  184.     if (tree[x].lazy_add != 0) {
  185.       push_add(lSon, l1, tree[x].lazy_add);
  186.       push_add(rSon, l2, tree[x].lazy_add);
  187.       tree[x].lazy_add = 0;
  188.     }
  189.     push_min_equal(lSon, l1, tree[x].max1);
  190.     push_min_equal(rSon, l2, tree[x].max1);
  191.     push_max_equal(lSon, l1, tree[x].min1);
  192.     push_max_equal(rSon, l2, tree[x].min1);
  193.   }
  194.  
  195.   void update_min(int x, int lx, int rx, int st, int dr, int val) {
  196.     if (tree[x].max1 <= val)
  197.       return;
  198.     if (st <= lx && rx <= dr && tree[x].max2 < val) {
  199.       push_min_equal(x, rx - lx + 1, val);
  200.       return;
  201.     }
  202.     push(x, lx, rx);
  203.     int mid = (lx + rx) >> 1;
  204.     if (st <= mid)
  205.       update_min(x << 1, lx, mid, st, dr, val);
  206.     if (mid < dr)
  207.       update_min(x << 1 | 1, mid + 1, rx, st, dr, val);
  208.     tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  209.   }
  210.  
  211.   void update_max(int x, int lx, int rx, int st, int dr, int val) {
  212.     if (val <= tree[x].min1)
  213.       return;
  214.     if (st <= lx && rx <= dr && val < tree[x].min2) {
  215.       push_max_equal(x, rx - lx + 1, val);
  216.       return;
  217.     }
  218.     push(x, lx, rx);
  219.     int mid = (lx + rx) >> 1;
  220.     if (st <= mid)
  221.       update_max(x << 1, lx, mid, st, dr, val);
  222.     if (mid < dr)
  223.       update_max(x << 1 | 1, mid + 1, rx, st, dr, val);
  224.     tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  225.   }
  226.  
  227.   void update_set(int x, int lx, int rx, int st, int dr, int val) {
  228.     if (st <= lx && rx <= dr) {
  229.       push_set(x, rx - lx + 1, val);
  230.       return;
  231.     }
  232.     push(x, lx, rx);
  233.     int mid = (lx + rx) >> 1;
  234.     if (st <= mid)
  235.       update_set(x << 1, lx, mid, st, dr, val);
  236.     if (mid < dr)
  237.       update_set(x << 1 | 1, mid + 1, rx, st, dr, val);
  238.     tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  239.   }
  240.  
  241.   void update_add(int x, int lx, int rx, int st, int dr, int val) {
  242.     if (st <= lx && rx <= dr) {
  243.       push_add(x, rx - lx + 1, val);
  244.       return;
  245.     }
  246.     push(x, lx, rx);
  247.     int mid = (lx + rx) >> 1;
  248.     if (st <= mid)
  249.       update_add(x << 1, lx, mid, st, dr, val);
  250.     if (mid < dr)
  251.       update_add(x << 1 | 1, mid + 1, rx, st, dr, val);
  252.     tree[x] = join(tree[x << 1], tree[x << 1 | 1]);
  253.   }
  254.  
  255.   int64 query_sum(int x, int lx, int rx, int st, int dr) {
  256.     if (st <= lx && rx <= dr)
  257.       return tree[x].sum;
  258.     push(x, lx, rx);
  259.     int mid = (lx + rx) >> 1;
  260.     int64 ans = 0;
  261.     if (st <= mid)
  262.       ans += query_sum(x << 1, lx, mid, st, dr);
  263.     if (mid < dr)
  264.       ans += query_sum(x << 1 | 1, mid + 1, rx, st, dr);
  265.     return ans;
  266.   }
  267.  
  268.   int64 query_min(int x, int lx, int rx, int st, int dr) {
  269.     if (st <= lx && rx <= dr)
  270.       return tree[x].min1;
  271.     push(x, lx, rx);
  272.     int mid = (lx + rx) >> 1;
  273.     int64 ans = INF;
  274.     if (st <= mid)
  275.       min_self(ans, query_min(x << 1, lx, mid, st, dr));
  276.     if (mid < dr)
  277.       min_self(ans, query_min(x << 1 | 1, mid + 1, rx, st, dr));
  278.     return ans;
  279.   }
  280.  
  281.   int64 query_max(int x, int lx, int rx, int st, int dr) {
  282.     if (st <= lx && rx <= dr)
  283.       return tree[x].max1;
  284.     push(x, lx, rx);
  285.     int mid = (lx + rx) >> 1;
  286.     int64 ans = 0;
  287.     if (st <= mid)
  288.       max_self(ans, query_max(x << 1, lx, mid, st, dr));
  289.     if (mid < dr)
  290.       max_self(ans, query_max(x << 1 | 1, mid + 1, rx, st, dr));
  291.     return ans;
  292.   }
  293.  
  294.   int64 query_gcd(int x, int lx, int rx, int st, int dr) {
  295.     if (st <= lx && rx <= dr) {
  296.       int64 ans = tree[x].diff_gcd;
  297.       ans = gcd(ans, tree[x].max1);
  298.       ans = gcd(ans, tree[x].min1);
  299.       for (int64 val : {tree[x].min2, tree[x].max2})
  300.         if (ABS(val) != INF) {
  301.           ans = gcd(ans, tree[x].max1 - val);
  302.           ans = gcd(ans, tree[x].min1 - val);
  303.           break;
  304.         }
  305.       return ans;
  306.     }
  307.     push(x, lx, rx);
  308.     int mid = (lx + rx) >> 1;
  309.     int64 ans = 0;
  310.     if (st <= mid)
  311.       ans = gcd(ans, query_gcd(x << 1, lx, mid, st, dr));
  312.     if (mid < dr)
  313.       ans = gcd(ans, query_gcd(x << 1 | 1, mid + 1, rx, st, dr));
  314.     return ans;
  315.   }
  316. };
  317.  
  318. void solve() {
  319.   int N;
  320.   cin >> N;
  321.   SegTree tree(N);
  322.   tree.build(1, 1, N);
  323.   int Q;
  324.   cin >> Q;
  325.   for (int q = 0; q < Q; ++q) {
  326.     int t;
  327.     cin >> t;
  328.     if (t < 5) {
  329.       int l, r, x;
  330.       cin >> l >> r >> x;
  331.       if (t == 1)
  332.         tree.update_min(1, 1, N, l, r, x);
  333.       if (t == 2)
  334.         tree.update_max(1, 1, N, l, r, x);
  335.       if (t == 3)
  336.         tree.update_set(1, 1, N, l, r, x);
  337.       if (t == 4)
  338.         tree.update_add(1, 1, N, l, r, x);
  339.     } else {
  340.       int l, r;
  341.       cin >> l >> r;
  342.       if (t == 5)
  343.         cout << tree.query_sum(1, 1, N, l, r);
  344.       if (t == 6)
  345.         cout << tree.query_min(1, 1, N, l, r);
  346.       if (t == 7)
  347.         cout << tree.query_max(1, 1, N, l, r);
  348.       if (t == 8)
  349.         cout << tree.query_gcd(1, 1, N, l, r);
  350.       cout << '\n';
  351.     }
  352.   }
  353. }
  354.  
  355. int main() {
  356.   fastIO();
  357.   solve();
  358.   return 0;
  359. }
  360.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×