API tools faq
paste
Advertisement
peltorator

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

peltorator
May 7th, 2021 (edited)
2,286
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.31 KB | None | 0 0
raw download clone embed print report
  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. }
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!