API tools faq
paste
Alex_tz307

Segment Tree Beats

Alex_tz307
Apr 22nd, 2021 (edited)
622
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.41 KB | None | 0 0
raw download clone embed print report
  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.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!