Guest User

Untitled

a guest
Sep 27th, 2021
207
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 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.   }
  33.   void upd(int l, int r, long long val) {
  34.     upd(1, 0, n - 1, l, r, val);
  35.   }
  36.   long long query(int x, int lx, int rx, int l, int r) {
  37.     push(x);
  38.     if(lx >= l && rx <= r) {
  39.       return t[x];
  40.     }
  41.     if(lx > r || rx < l) {return 0;}
  42.     int m = (lx + rx) / 2;
  43.     return query(2 * x, lx, m, l, r) + query(2 * x + 1, m + 1, rx, l, r);
  44.   }
  45.   long long query(int l, int r) {
  46.     return query(1, 0, n - 1, l, r);
  47.   }
  48. };
  49.  
  50. int main() {
  51.   ios::sync_with_stdio(false);
  52.   cin.tie(0);
  53.   int m;
  54.   cin >> n >> m;
  55.   SegmentTree st;
  56.   for (int i = 0; i<m; i++) {
  57.     int type;
  58.     cin >> type;
  59.     if(type == 1) {
  60.       long long l,r,v;
  61.       cin >> l >> r >> v;
  62.       r--;
  63.       st.upd(l, r, v);
  64.       continue;
  65.     }
  66.     int l, r;
  67.     cin >> l >> r;
  68.     r--;
  69.     cout << st.query(l, r) << '\n';
  70.   }
  71.   return 0;
  72. }
  73.  
  74.  
Advertisement
Add Comment
Please, Sign In to add comment