API tools faq
paste
Alex_tz307

SEGMENT TREE BEATS COMPLET

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