peltorator

Extended Ji Driver Segment Tree (min=, max=, +=, =, sum, max, min on a segment)

May 7th, 2021 (edited)
791
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. struct JiDriverSegmentTree {
  6.     static const int T = (1 << 20);
  7.     static const long long INF = 1e15 + 7;
  8.  
  9.     struct Node {
  10.         long long min;
  11.         int minCnt;
  12.         long long secondMin;
  13.  
  14.         long long max;
  15.         int maxCnt;
  16.         long long secondMax;
  17.  
  18.         long long sum;
  19.  
  20.         long long pushSum;
  21.         long long pushEq;
  22.         // If we have pushEq, no other pushes should be made. They're all combined together in pushEq.
  23.         // Otherwise we first apply pushSum and then min= and max= pushes (in any order btw).
  24.     } tree[T];
  25.  
  26.     int n;
  27.  
  28.     void doPushEq(int v, int l, int r, long long val) {
  29.         tree[v].min = tree[v].max = tree[v].pushEq = val;
  30.         tree[v].minCnt = tree[v].maxCnt = r - l;
  31.         tree[v].secondMax = -INF;
  32.         tree[v].secondMin = INF;
  33.  
  34.         tree[v].sum = val * (r - l);
  35.         tree[v].pushSum = 0;
  36.     }
  37.  
  38.     void doPushMinEq(int v, int l, int r, long long val) {
  39.         if (tree[v].min >= val) {
  40.             doPushEq(v, l, r, val);
  41.         } else if (tree[v].max > val) {
  42.             if (tree[v].secondMin == tree[v].max) {
  43.                 tree[v].secondMin = val;
  44.             }
  45.             tree[v].sum -= (tree[v].max - val) * tree[v].maxCnt;
  46.             tree[v].max = val;
  47.         }
  48.     }
  49.  
  50.     void doPushMaxEq(int v, int l, int r, long long val) {
  51.         if (tree[v].max <= val) {
  52.             doPushEq(v, l, r, val);
  53.         } else if (tree[v].min < val) {
  54.             if (tree[v].secondMax == tree[v].min) {
  55.                 tree[v].secondMax = val;
  56.             }
  57.             tree[v].sum += (val - tree[v].min) * tree[v].minCnt;
  58.             tree[v].min = val;
  59.         }
  60.     }
  61.  
  62.     void doPushSum(int v, int l, int r, long long val) {
  63.         if (tree[v].min == tree[v].max) {
  64.             doPushEq(v, l, r, tree[v].min + val);
  65.         } else {
  66.             tree[v].max += val;
  67.             if (tree[v].secondMax != -INF) {
  68.                 tree[v].secondMax += val;
  69.             }
  70.  
  71.             tree[v].min += val;
  72.             if (tree[v].secondMin != INF) {
  73.                 tree[v].secondMin += val;
  74.             }
  75.  
  76.             tree[v].sum += (r - l) * val;
  77.             tree[v].pushSum += val;
  78.         }
  79.     }
  80.  
  81.     void pushToChildren(int v, int l, int r) {
  82.         if (l + 1 == r) {
  83.             return;
  84.         }
  85.         int mid = (r + l) / 2;
  86.         if (tree[v].pushEq != -1) {
  87.             doPushEq(2 * v, l, mid, tree[v].pushEq);
  88.             doPushEq(2 * v + 1, mid, r, tree[v].pushEq);
  89.             tree[v].pushEq = -1;
  90.         } else {
  91.             doPushSum(2 * v, l, mid, tree[v].pushSum);
  92.             doPushSum(2 * v + 1, mid, r, tree[v].pushSum);
  93.             tree[v].pushSum = 0;
  94.  
  95.             doPushMinEq(2 * v, l, mid, tree[v].max);
  96.             doPushMinEq(2 * v + 1, mid, r, tree[v].max);
  97.  
  98.             doPushMaxEq(2 * v, l, mid, tree[v].min);
  99.             doPushMaxEq(2 * v + 1, mid, r, tree[v].min);
  100.         }
  101.     }
  102.  
  103.     void updateFromChildren(int v) {
  104.         tree[v].sum = tree[2 * v].sum + tree[2 * v + 1].sum;
  105.  
  106.         tree[v].max = max(tree[2 * v].max, tree[2 * v + 1].max);
  107.         tree[v].secondMax = max(tree[2 * v].secondMax, tree[2 * v + 1].secondMax);
  108.         tree[v].maxCnt = 0;
  109.         if (tree[2 * v].max == tree[v].max) {
  110.             tree[v].maxCnt += tree[2 * v].maxCnt;
  111.         } else {
  112.             tree[v].secondMax = max(tree[v].secondMax, tree[2 * v].max);
  113.         }
  114.         if (tree[2 * v + 1].max == tree[v].max) {
  115.             tree[v].maxCnt += tree[2 * v + 1].maxCnt;
  116.         } else {
  117.             tree[v].secondMax = max(tree[v].secondMax, tree[2 * v + 1].max);
  118.         }
  119.  
  120.         tree[v].min = min(tree[2 * v].min, tree[2 * v + 1].min);
  121.         tree[v].secondMin = min(tree[2 * v].secondMin, tree[2 * v + 1].secondMin);
  122.         tree[v].minCnt = 0;
  123.         if (tree[2 * v].min == tree[v].min) {
  124.             tree[v].minCnt += tree[2 * v].minCnt;
  125.         } else {
  126.             tree[v].secondMin = min(tree[v].secondMin, tree[2 * v].min);
  127.         }
  128.         if (tree[2 * v + 1].min == tree[v].min) {
  129.             tree[v].minCnt += tree[2 * v + 1].minCnt;
  130.         } else {
  131.             tree[v].secondMin = min(tree[v].secondMin, tree[2 * v + 1].min);
  132.         }
  133.     }
  134.  
  135.     void build(int v, int l, int r, const vector<int>& inputArray) {
  136.         tree[v].pushSum = 0;
  137.         tree[v].pushEq = -1;
  138.         if (l + 1 == r) {
  139.             tree[v].max = inputArray[l];
  140.             tree[v].secondMax = -INF;
  141.             tree[v].maxCnt = 1;
  142.  
  143.             tree[v].min = inputArray[l];
  144.             tree[v].secondMin = INF;
  145.             tree[v].minCnt = 1;
  146.  
  147.             tree[v].sum = inputArray[l];
  148.         } else {
  149.             int mid = (r + l) / 2;
  150.             build(2 * v, l, mid, inputArray);
  151.             build(2 * v + 1, mid, r, inputArray);
  152.             updateFromChildren(v);
  153.         }
  154.     }
  155.  
  156.     void build(const vector<int>& inputArray) {
  157.         n = inputArray.size();
  158.         build(1, 0, n, inputArray);
  159.     }
  160.  
  161.     void updateMinEq(int v, int l, int r, int ql, int qr, int val) {
  162.         if (qr <= l || r <= ql || tree[v].max <= val) {
  163.             return;
  164.         }
  165.         if (ql <= l && r <= qr && tree[v].secondMax < val) {
  166.             doPushMinEq(v, l, r, val);
  167.             return;
  168.         }
  169.         pushToChildren(v, l, r);
  170.         int mid = (r + l) / 2;
  171.         updateMinEq(2 * v, l, mid, ql, qr, val);
  172.         updateMinEq(2 * v + 1, mid, r, ql, qr, val);
  173.         updateFromChildren(v);
  174.     }
  175.  
  176.     void updateMinEq(int ql, int qr, int val) {
  177.         updateMinEq(1, 0, n, ql, qr, val);
  178.     }
  179.  
  180.     void updateMaxEq(int v, int l, int r, int ql, int qr, int val) {
  181.         if (qr <= l || r <= ql || tree[v].min >= val) {
  182.             return;
  183.         }
  184.         if (ql <= l && r <= qr && tree[v].secondMin > val) {
  185.             doPushMaxEq(v, l, r, val);
  186.             return;
  187.         }
  188.         pushToChildren(v, l, r);
  189.         int mid = (r + l) / 2;
  190.         updateMaxEq(2 * v, l, mid, ql, qr, val);
  191.         updateMaxEq(2 * v + 1, mid, r, ql, qr, val);
  192.         updateFromChildren(v);
  193.     }
  194.  
  195.     void updateMaxEq(int ql, int qr, int val) {
  196.         updateMaxEq(1, 0, n, ql, qr, val);
  197.     }
  198.  
  199.     void updateEq(int v, int l, int r, int ql, int qr, int val) {
  200.         if (qr <= l || r <= ql) {
  201.             return;
  202.         }
  203.         if (ql <= l && r <= qr) {
  204.             doPushEq(v, l, r, val);
  205.             return;
  206.         }
  207.         pushToChildren(v, l, r);
  208.         int mid = (r + l) / 2;
  209.         updateEq(2 * v, l, mid, ql, qr, val);
  210.         updateEq(2 * v + 1, mid, r, ql, qr, val);
  211.         updateFromChildren(v);
  212.     }
  213.  
  214.     void updateEq(int ql, int qr, int val) {
  215.         updateEq(1, 0, n, ql, qr, val);
  216.     }
  217.  
  218.     void updatePlusEq(int v, int l, int r, int ql, int qr, int val) {
  219.         if (qr <= l || r <= ql) {
  220.             return;
  221.         }
  222.         if (ql <= l && r <= qr) {
  223.             doPushSum(v, l, r, val);
  224.             return;
  225.         }
  226.         pushToChildren(v, l, r);
  227.         int mid = (r + l) / 2;
  228.         updatePlusEq(2 * v, l, mid, ql, qr, val);
  229.         updatePlusEq(2 * v + 1, mid, r, ql, qr, val);
  230.         updateFromChildren(v);
  231.     }
  232.  
  233.     void updatePlusEq(int ql, int qr, int val) {
  234.         updatePlusEq(1, 0, n, ql, qr, val);
  235.     }
  236.  
  237.     long long findSum(int v, int l, int r, int ql, int qr) {
  238.         if (qr <= l || r <= ql) {
  239.             return 0;
  240.         }
  241.         if (ql <= l && r <= qr) {
  242.             return tree[v].sum;
  243.         }
  244.         pushToChildren(v, l, r);
  245.         int mid = (r + l) / 2;
  246.         return findSum(2 * v, l, mid, ql, qr) + findSum(2 * v + 1, mid, r, ql, qr);
  247.     }
  248.  
  249.     long long findSum(int ql, int qr) {
  250.         return findSum(1, 0, n, ql, qr);
  251.     }
  252.  
  253.     long long findMin(int v, int l, int r, int ql, int qr) {
  254.         if (qr <= l || r <= ql) {
  255.             return INF;
  256.         }
  257.         if (ql <= l && r <= qr) {
  258.             return tree[v].min;
  259.         }
  260.         pushToChildren(v, l, r);
  261.         int mid = (r + l) / 2;
  262.         return min(findMin(2 * v, l, mid, ql, qr), findMin(2 * v + 1, mid, r, ql, qr));
  263.     }
  264.  
  265.     long long findMin(int ql, int qr) {
  266.         return findMin(1, 0, n, ql, qr);
  267.     }
  268.  
  269.     long long findMax(int v, int l, int r, int ql, int qr) {
  270.         if (qr <= l || r <= ql) {
  271.             return -INF;
  272.         }
  273.         if (ql <= l && r <= qr) {
  274.             return tree[v].max;
  275.         }
  276.         pushToChildren(v, l, r);
  277.         int mid = (r + l) / 2;
  278.         return max(findMax(2 * v, l, mid, ql, qr), findMax(2 * v + 1, mid, r, ql, qr));
  279.     }
  280.  
  281.     long long findMax(int ql, int qr) {
  282.         return findMax(1, 0, n, ql, qr);
  283.     }
  284. } segTree;
  285.  
  286. int main() {
  287.     ios::sync_with_stdio(0);
  288.     cin.tie(0);
  289.     int n;
  290.     cin >> n;
  291.     vector<int> inputArray(n);
  292.     for (int &val : inputArray) {
  293.         cin >> val;
  294.     }
  295.     segTree.build(inputArray);
  296.     int q;
  297.     cin >> q;
  298.     for (int i = 0; i < q; i++) {
  299.         int type, ql, qr;
  300.         cin >> type >> ql >> qr;
  301.         ql--;
  302.         if (type == 1) {
  303.             int k;
  304.             cin >> k;
  305.             segTree.updateMinEq(ql, qr, k);
  306.         } else if (type == 2) {
  307.             int k;
  308.             cin >> k;
  309.             segTree.updatePlusEq(ql, qr, k);
  310.         } else {
  311.             cout << segTree.findSum(ql, qr) << '\n';
  312.         }
  313.     }
  314.     return 0;
  315. }
RAW Paste Data