Advertisement
Guest User

Untitled

a guest
Sep 27th, 2021
309
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int maxN = 1e5;
  6.  
  7. int n;
  8.  
  9. struct SegmentTree {
  10.   vector<long long> t = vector<long long> (maxN * 4);
  11.   vector<long long> lazy = vector<long long> (maxN * 4);
  12.  
  13.   void push(int x) {
  14.     lazy[2 * x] += lazy[x];
  15.     lazy[2 * x + 1] += lazy[x];
  16.     t[2 * x] += lazy[x];
  17.     t[2 * x + 1] += lazy[x];
  18.     lazy[x] = 0;
  19.   }
  20.   void upd(int x, int lx, int rx, int l, int r, long long val) {
  21.     push(x);
  22.     if(lx >= l && rx <= r) {
  23.       t[x] += val * (rx - lx + 1);
  24.       lazy[x] += val;
  25.       return;
  26.     }
  27.     if(lx > r || rx < l) {return;}
  28.     push(x);
  29.     int m = (lx + rx) / 2;
  30.     upd(2 * x, lx, m, l, r, val);
  31.     upd(2 * x + 1, m + 1, rx, l, r, val);
  32.     t[x] = t[2 * x] + t[2 * x + 1];
  33.   }
  34.   void upd(int l, int r, long long val) {
  35.     upd(1, 0, n - 1, l, r, val);
  36.   }
  37.   long long query(int x, int lx, int rx, int l, int r) {
  38.     push(x);
  39.     if(lx >= l && rx <= r) {
  40.       return t[x];
  41.     }
  42.     if(lx > r || rx < l) {return 0;}
  43.     int m = (lx + rx) / 2;
  44.     long long f = query(2 * x, lx, m, l, r) , s = query(2 * x + 1, m + 1, rx, l, r);
  45.     t[x] = t[2 * x + 1] + t[2 * x];
  46.     return f + s;
  47.   }
  48.   long long query(int l, int r) {
  49.     return query(1, 0, n - 1, l, r);
  50.   }
  51. };
  52.  
  53. int main() {
  54.   ios::sync_with_stdio(false);
  55.   cin.tie(0);
  56.   int m;
  57.   cin >> n >> m;
  58.   SegmentTree st;
  59.   for (int i = 0; i<m; i++) {
  60.     int type;
  61.     cin >> type;
  62.     if(type == 1) {
  63.       long long l,r,v;
  64.       cin >> l >> r >> v;
  65.       r--;
  66.       st.upd(l, r, v);
  67.       continue;
  68.     }
  69.     int l, r;
  70.     cin >> l >> r;
  71.     r--;
  72.     cout << st.query(l, r) << '\n';
  73.   }
  74.   return 0;
  75. }
  76.  
  77.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement