peltorator

%=, =, sum on a segment

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