API tools faq
paste
Advertisement
peltorator

min=, max=, +=, =, sum, max, min, GCD on a segment

peltorator
May 7th, 2021
2,660
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.12 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long gcd(long long a, long long b) { // always positive
  6.     a = abs(a);
  7.     b = abs(b);
  8.     while (a) {
  9.         b %= a;
  10.         swap(a, b);
  11.     }
  12.     return b;
  13. }
  14.  
  15. struct JiDriverSegmentTree {
  16.     static const int T = (1 << 20);
  17.     static const long long INF = 1e15 + 7;
  18.  
  19.     struct Node {
  20.         long long min;
  21.         int minCnt;
  22.         long long secondMin;
  23.  
  24.         long long max;
  25.         int maxCnt;
  26.         long long secondMax;
  27.  
  28.         long long sum;
  29.         long long diffGcd;
  30.  
  31.         long long pushSum;
  32.         long long pushEq;
  33.         // If we have pushEq, no other pushes should be made. They're all combined together in pushEq.
  34.         // Otherwise we first apply pushSum and then min= and max= pushes (in any order btw).
  35.     } tree[T];
  36.  
  37.     int n;
  38.  
  39.     void doPushEq(int v, int l, int r, long long val) {
  40.         tree[v].min = tree[v].max = tree[v].pushEq = val;
  41.         tree[v].minCnt = tree[v].maxCnt = r - l;
  42.         tree[v].secondMax = -INF;
  43.         tree[v].secondMin = INF;
  44.  
  45.         tree[v].sum = val * (r - l);
  46.         tree[v].diffGcd = 0;
  47.         tree[v].pushSum = 0;
  48.     }
  49.  
  50.     void doPushMinEq(int v, int l, int r, long long val) {
  51.         if (tree[v].min >= val) {
  52.             doPushEq(v, l, r, val);
  53.         } else if (tree[v].max > val) {
  54.             if (tree[v].secondMin == tree[v].max) {
  55.                 tree[v].secondMin = val;
  56.             }
  57.             tree[v].sum -= (tree[v].max - val) * tree[v].maxCnt;
  58.             tree[v].max = val;
  59.         }
  60.     }
  61.  
  62.     void doPushMaxEq(int v, int l, int r, long long val) {
  63.         if (tree[v].max <= val) {
  64.             doPushEq(v, l, r, val);
  65.         } else if (tree[v].min < val) {
  66.             if (tree[v].secondMax == tree[v].min) {
  67.                 tree[v].secondMax = val;
  68.             }
  69.             tree[v].sum += (val - tree[v].min) * tree[v].minCnt;
  70.             tree[v].min = val;
  71.         }
  72.     }
  73.  
  74.     void doPushSum(int v, int l, int r, long long val) {
  75.         if (tree[v].min == tree[v].max) {
  76.             doPushEq(v, l, r, tree[v].min + val);
  77.         } else {
  78.             tree[v].max += val;
  79.             if (tree[v].secondMax != -INF) {
  80.                 tree[v].secondMax += val;
  81.             }
  82.  
  83.             tree[v].min += val;
  84.             if (tree[v].secondMin != INF) {
  85.                 tree[v].secondMin += val;
  86.             }
  87.  
  88.             tree[v].sum += (r - l) * val;
  89.             tree[v].pushSum += val;
  90.         }
  91.     }
  92.  
  93.     void pushToChildren(int v, int l, int r) {
  94.         if (l + 1 == r) {
  95.             return;
  96.         }
  97.         int mid = (r + l) / 2;
  98.         if (tree[v].pushEq != -1) {
  99.             doPushEq(2 * v, l, mid, tree[v].pushEq);
  100.             doPushEq(2 * v + 1, mid, r, tree[v].pushEq);
  101.             tree[v].pushEq = -1;
  102.         } else {
  103.             doPushSum(2 * v, l, mid, tree[v].pushSum);
  104.             doPushSum(2 * v + 1, mid, r, tree[v].pushSum);
  105.             tree[v].pushSum = 0;
  106.  
  107.             doPushMinEq(2 * v, l, mid, tree[v].max);
  108.             doPushMinEq(2 * v + 1, mid, r, tree[v].max);
  109.  
  110.             doPushMaxEq(2 * v, l, mid, tree[v].min);
  111.             doPushMaxEq(2 * v + 1, mid, r, tree[v].min);
  112.         }
  113.     }
  114.  
  115.     void updateFromChildren(int v) {
  116.         tree[v].sum = tree[2 * v].sum + tree[2 * v + 1].sum;
  117.  
  118.         tree[v].max = max(tree[2 * v].max, tree[2 * v + 1].max);
  119.         tree[v].secondMax = max(tree[2 * v].secondMax, tree[2 * v + 1].secondMax);
  120.         tree[v].maxCnt = 0;
  121.         if (tree[2 * v].max == tree[v].max) {
  122.             tree[v].maxCnt += tree[2 * v].maxCnt;
  123.         } else {
  124.             tree[v].secondMax = max(tree[v].secondMax, tree[2 * v].max);
  125.         }
  126.         if (tree[2 * v + 1].max == tree[v].max) {
  127.             tree[v].maxCnt += tree[2 * v + 1].maxCnt;
  128.         } else {
  129.             tree[v].secondMax = max(tree[v].secondMax, tree[2 * v + 1].max);
  130.         }
  131.  
  132.         tree[v].min = min(tree[2 * v].min, tree[2 * v + 1].min);
  133.         tree[v].secondMin = min(tree[2 * v].secondMin, tree[2 * v + 1].secondMin);
  134.         tree[v].minCnt = 0;
  135.         if (tree[2 * v].min == tree[v].min) {
  136.             tree[v].minCnt += tree[2 * v].minCnt;
  137.         } else {
  138.             tree[v].secondMin = min(tree[v].secondMin, tree[2 * v].min);
  139.         }
  140.         if (tree[2 * v + 1].min == tree[v].min) {
  141.             tree[v].minCnt += tree[2 * v + 1].minCnt;
  142.         } else {
  143.             tree[v].secondMin = min(tree[v].secondMin, tree[2 * v + 1].min);
  144.         }
  145.  
  146.         tree[v].diffGcd = gcd(tree[2 * v].diffGcd, tree[2 * v + 1].diffGcd);
  147.  
  148.         long long anyLeft = tree[2 * v].secondMax; // any value that's not equal to left child max and min
  149.         long long anyRight = tree[2 * v + 1].secondMax; // any value that's not equal to right child max and min
  150.         if (anyLeft != -INF && anyLeft != tree[2 * v].min && anyRight != -INF && anyRight != tree[2 * v + 1].min) {
  151.             tree[v].diffGcd = gcd(tree[v].diffGcd, anyLeft - anyRight); // connect two spanning trees
  152.         }
  153.  
  154.         long long any = -1; // any value that's not equal to current vertex max and min
  155.         if (anyLeft != -INF && anyLeft != tree[2 * v].min) {
  156.             any = anyLeft;
  157.         } else if (anyRight != -INF && anyRight != tree[2 * v + 1].min) {
  158.             any = anyRight;
  159.         }
  160.  
  161.         // adding all values that are not max and min anymore to diffGcd
  162.         for (long long val : {tree[2 * v].min, tree[2 * v].max, tree[2 * v + 1].min, tree[2 * v + 1].max}) {
  163.             if (val != tree[v].min && val != tree[v].max) {
  164.                 if (any != -1) {
  165.                     tree[v].diffGcd = gcd(tree[v].diffGcd, val - any);
  166.                 } else {
  167.                     any = val;
  168.                 }
  169.             }
  170.         }
  171.     }
  172.  
  173.     void build(int v, int l, int r, const vector<int>& inputArray) {
  174.         tree[v].pushSum = 0;
  175.         tree[v].pushEq = -1;
  176.         if (l + 1 == r) {
  177.             tree[v].max = inputArray[l];
  178.             tree[v].secondMax = -INF;
  179.             tree[v].maxCnt = 1;
  180.  
  181.             tree[v].min = inputArray[l];
  182.             tree[v].secondMin = INF;
  183.             tree[v].minCnt = 1;
  184.  
  185.             tree[v].diffGcd = 0;
  186.             tree[v].sum = inputArray[l];
  187.         } else {
  188.             int mid = (r + l) / 2;
  189.             build(2 * v, l, mid, inputArray);
  190.             build(2 * v + 1, mid, r, inputArray);
  191.             updateFromChildren(v);
  192.         }
  193.     }
  194.  
  195.     void build(const vector<int>& inputArray) {
  196.         n = inputArray.size();
  197.         build(1, 0, n, inputArray);
  198.     }
  199.  
  200.     void updateMinEq(int v, int l, int r, int ql, int qr, int val) {
  201.         if (qr <= l || r <= ql || tree[v].max <= val) {
  202.             return;
  203.         }
  204.         if (ql <= l && r <= qr && tree[v].secondMax < val) {
  205.             doPushMinEq(v, l, r, val);
  206.             return;
  207.         }
  208.         pushToChildren(v, l, r);
  209.         int mid = (r + l) / 2;
  210.         updateMinEq(2 * v, l, mid, ql, qr, val);
  211.         updateMinEq(2 * v + 1, mid, r, ql, qr, val);
  212.         updateFromChildren(v);
  213.     }
  214.  
  215.     void updateMinEq(int ql, int qr, int val) {
  216.         updateMinEq(1, 0, n, ql, qr, val);
  217.     }
  218.  
  219.     void updateMaxEq(int v, int l, int r, int ql, int qr, int val) {
  220.         if (qr <= l || r <= ql || tree[v].min >= val) {
  221.             return;
  222.         }
  223.         if (ql <= l && r <= qr && tree[v].secondMin > val) {
  224.             doPushMaxEq(v, l, r, val);
  225.             return;
  226.         }
  227.         pushToChildren(v, l, r);
  228.         int mid = (r + l) / 2;
  229.         updateMaxEq(2 * v, l, mid, ql, qr, val);
  230.         updateMaxEq(2 * v + 1, mid, r, ql, qr, val);
  231.         updateFromChildren(v);
  232.     }
  233.  
  234.     void updateMaxEq(int ql, int qr, int val) {
  235.         updateMaxEq(1, 0, n, ql, qr, val);
  236.     }
  237.  
  238.     void updateEq(int v, int l, int r, int ql, int qr, int val) {
  239.         if (qr <= l || r <= ql) {
  240.             return;
  241.         }
  242.         if (ql <= l && r <= qr) {
  243.             doPushEq(v, l, r, val);
  244.             return;
  245.         }
  246.         pushToChildren(v, l, r);
  247.         int mid = (r + l) / 2;
  248.         updateEq(2 * v, l, mid, ql, qr, val);
  249.         updateEq(2 * v + 1, mid, r, ql, qr, val);
  250.         updateFromChildren(v);
  251.     }
  252.  
  253.     void updateEq(int ql, int qr, int val) {
  254.         updateEq(1, 0, n, ql, qr, val);
  255.     }
  256.  
  257.     void updatePlusEq(int v, int l, int r, int ql, int qr, int val) {
  258.         if (qr <= l || r <= ql) {
  259.             return;
  260.         }
  261.         if (ql <= l && r <= qr) {
  262.             doPushSum(v, l, r, val);
  263.             return;
  264.         }
  265.         pushToChildren(v, l, r);
  266.         int mid = (r + l) / 2;
  267.         updatePlusEq(2 * v, l, mid, ql, qr, val);
  268.         updatePlusEq(2 * v + 1, mid, r, ql, qr, val);
  269.         updateFromChildren(v);
  270.     }
  271.  
  272.     void updatePlusEq(int ql, int qr, int val) {
  273.         updatePlusEq(1, 0, n, ql, qr, val);
  274.     }
  275.  
  276.     long long findSum(int v, int l, int r, int ql, int qr) {
  277.         if (qr <= l || r <= ql) {
  278.             return 0;
  279.         }
  280.         if (ql <= l && r <= qr) {
  281.             return tree[v].sum;
  282.         }
  283.         pushToChildren(v, l, r);
  284.         int mid = (r + l) / 2;
  285.         return findSum(2 * v, l, mid, ql, qr) + findSum(2 * v + 1, mid, r, ql, qr);
  286.     }
  287.  
  288.     long long findSum(int ql, int qr) {
  289.         return findSum(1, 0, n, ql, qr);
  290.     }
  291.  
  292.     long long findMin(int v, int l, int r, int ql, int qr) {
  293.         if (qr <= l || r <= ql) {
  294.             return INF;
  295.         }
  296.         if (ql <= l && r <= qr) {
  297.             return tree[v].min;
  298.         }
  299.         pushToChildren(v, l, r);
  300.         int mid = (r + l) / 2;
  301.         return min(findMin(2 * v, l, mid, ql, qr), findMin(2 * v + 1, mid, r, ql, qr));
  302.     }
  303.  
  304.     long long findMin(int ql, int qr) {
  305.         return findMin(1, 0, n, ql, qr);
  306.     }
  307.  
  308.     long long findMax(int v, int l, int r, int ql, int qr) {
  309.         if (qr <= l || r <= ql) {
  310.             return -INF;
  311.         }
  312.         if (ql <= l && r <= qr) {
  313.             return tree[v].max;
  314.         }
  315.         pushToChildren(v, l, r);
  316.         int mid = (r + l) / 2;
  317.         return max(findMax(2 * v, l, mid, ql, qr), findMax(2 * v + 1, mid, r, ql, qr));
  318.     }
  319.  
  320.     long long findMax(int ql, int qr) {
  321.         return findMax(1, 0, n, ql, qr);
  322.     }
  323.  
  324.     long long findGcd(int v, int l, int r, int ql, int qr) {
  325.         if (qr <= l || r <= ql) {
  326.             return 0;
  327.         }
  328.         if (ql <= l && r <= qr) {
  329.             long long ans = tree[v].diffGcd;
  330.             if (tree[v].secondMax != -INF) {
  331.                 ans = gcd(ans, tree[v].secondMax - tree[v].max);
  332.             }
  333.             if (tree[v].secondMin != INF) {
  334.                 ans = gcd(ans, tree[v].secondMin - tree[v].min);
  335.             }
  336.             ans = gcd(ans, tree[v].max);
  337.             return ans;
  338.         }
  339.         pushToChildren(v, l, r);
  340.         int mid = (r + l) / 2;
  341.         return gcd(findGcd(2 * v, l, mid, ql, qr), findGcd(2 * v + 1, mid, r, ql, qr));
  342.     }
  343.  
  344.     long long findGcd(int ql, int qr) {
  345.         return findGcd(1, 0, n, ql, qr);
  346.     }
  347. } segTree;
  348.  
  349. int main() {
  350.     ios::sync_with_stdio(0);
  351.     cin.tie(0);
  352.     int n;
  353.     cin >> n;
  354.     vector<int> inputArray(n);
  355.     for (int &val : inputArray) {
  356.         cin >> val;
  357.     }
  358.     segTree.build(inputArray);
  359.     int q;
  360.     cin >> q;
  361.     for (int i = 0; i < q; i++) {
  362.         int type, ql, qr;
  363.         cin >> type >> ql >> qr;
  364.         ql--;
  365.         if (type == 1) {
  366.             long long k;
  367.             cin >> k;
  368.             segTree.updateMinEq(ql, qr, k);
  369.         } else if (type == 2) {
  370.             long long k;
  371.             cin >> k;
  372.             segTree.updateMaxEq(ql, qr, k);
  373.         } else if (type == 3) {
  374.             long long k;
  375.             cin >> k;
  376.             segTree.updateEq(ql, qr, k);
  377.         } else if (type == 4) {
  378.             long long k;
  379.             cin >> k;
  380.             segTree.updatePlusEq(ql, qr, k);
  381.         } else if (type == 5) {
  382.             cout << segTree.findSum(ql, qr) << '\n';
  383.         } else if (type == 6) {
  384.             cout << segTree.findMin(ql, qr) << '\n';
  385.         } else if (type == 7) {
  386.             cout << segTree.findMax(ql, qr) << '\n';
  387.         } else {
  388.             cout << segTree.findGcd(ql, qr) << '\n';
  389.         }
  390.     }
  391.     return 0;
  392. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!