peltorator

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

May 7th, 2021 (edited)
349
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 int INF = 1e9 + 7;
  8.  
  9.     struct Node {
  10.         int max; // We can not store pushMax because we can just think of max as pushMax
  11.         int maxCnt;
  12.         int secondMax;
  13.         long long sum;
  14.     } tree[T];
  15.  
  16.     int n;
  17.  
  18.     void doPushMinEq(int v, int val) {
  19.         if (tree[v].max > val) {
  20.             tree[v].sum -= 1LL * (tree[v].max - val) * tree[v].maxCnt;
  21.             tree[v].max = val;
  22.         }
  23.     }
  24.  
  25.     void pushToChildren(int v) {
  26.         doPushMinEq(2 * v, tree[v].max);
  27.         doPushMinEq(2 * v + 1, tree[v].max);
  28.     }
  29.  
  30.     void updateFromChildren(int v) {
  31.         tree[v].sum = tree[2 * v].sum + tree[2 * v + 1].sum;
  32.         tree[v].max = max(tree[2 * v].max, tree[2 * v + 1].max);
  33.         tree[v].secondMax = max(tree[2 * v].secondMax, tree[2 * v + 1].secondMax);
  34.         tree[v].maxCnt = 0;
  35.         if (tree[2 * v].max == tree[v].max) {
  36.             tree[v].maxCnt += tree[2 * v].maxCnt;
  37.         } else {
  38.             tree[v].secondMax = max(tree[v].secondMax, tree[2 * v].max);
  39.         }
  40.         if (tree[2 * v + 1].max == tree[v].max) {
  41.             tree[v].maxCnt += tree[2 * v + 1].maxCnt;
  42.         } else {
  43.             tree[v].secondMax = max(tree[v].secondMax, tree[2 * v + 1].max);
  44.         }
  45.     }
  46.  
  47.     void build(int v, int l, int r, const vector<int>& inputArray) {
  48.         if (l + 1 == r) {
  49.             tree[v].max = tree[v].sum = inputArray[l];
  50.             tree[v].maxCnt = 1;
  51.             tree[v].secondMax = -INF;
  52.         } else {
  53.             int mid = (r + l) / 2;
  54.             build(2 * v, l, mid, inputArray);
  55.             build(2 * v + 1, mid, r, inputArray);
  56.             updateFromChildren(v);
  57.         }
  58.     }
  59.  
  60.     void build(const vector<int>& inputArray) {
  61.         n = inputArray.size();
  62.         build(1, 0, n, inputArray);
  63.     }
  64.  
  65.     void updateMineq(int v, int l, int r, int ql, int qr, int val) {
  66.         if (qr <= l || r <= ql || tree[v].max <= val) {
  67.             return;
  68.         }
  69.         if (ql <= l && r <= qr && tree[v].secondMax < val) {
  70.             doPushMinEq(v, val);
  71.             return;
  72.         }
  73.         pushToChildren(v);
  74.         int mid = (r + l) / 2;
  75.         updateMineq(2 * v, l, mid, ql, qr, val);
  76.         updateMineq(2 * v + 1, mid, r, ql, qr, val);
  77.         updateFromChildren(v);
  78.     }
  79.  
  80.     void updateMineq(int ql, int qr, int val) {
  81.         updateMineq(1, 0, n, ql, qr, val);
  82.     }
  83.  
  84.     long long findSum(int v, int l, int r, int ql, int qr) {
  85.         if (qr <= l || r <= ql) {
  86.             return 0;
  87.         }
  88.         if (ql <= l && r <= qr) {
  89.             return tree[v].sum;
  90.         }
  91.         pushToChildren(v);
  92.         int mid = (r + l) / 2;
  93.         return findSum(2 * v, l, mid, ql, qr) + findSum(2 * v + 1, mid, r, ql, qr);
  94.     }
  95.  
  96.     long long findSum(int ql, int qr) {
  97.         return findSum(1, 0, n, ql, qr);
  98.     }
  99. } segTree;
  100.  
  101. int main() {
  102.     ios::sync_with_stdio(0);
  103.     cin.tie(0);
  104.     int n;
  105.     cin >> n;
  106.     vector<int> inputArray(n);
  107.     for (int &val : inputArray) {
  108.         cin >> val;
  109.     }
  110.     segTree.build(inputArray);
  111.     int q;
  112.     cin >> q;
  113.     for (int i = 0; i < q; i++) {
  114.         int type, ql, qr;
  115.         cin >> type >> ql >> qr;
  116.         ql--;
  117.         if (type == 1) {
  118.             int k;
  119.             cin >> k;
  120.             segTree.updateMineq(ql, qr, k);
  121.         } else {
  122.             cout << segTree.findSum(ql, qr) << '\n';
  123.         }
  124.     }
  125.     return 0;
  126. }
RAW Paste Data