peltorator

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

May 7th, 2021
929
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.  
  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. }
RAW Paste Data