Advertisement
oleg_drawer

do array [set_segm, get_segm]

Jun 3rd, 2020
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. //do array [set_segm, get_segm]
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. vector<ll> a;
  7. vector<bool> all;
  8.  
  9. void push(int v, int l, int r){
  10.     all[v*2 + 1] = true;
  11.     all[v*2 + 2] = true;
  12.     ll y = a[v] / (r-l);
  13.     int m = (r+l)/2;
  14.     a[2*v+1] = y* (m - l);
  15.     a[2*v+2] = y* (r - m);
  16. }
  17.  
  18. void setx(int v, int l, int r, int lr, int rr, ll y){
  19.     if(r <= lr || rr <= l)
  20.         return;
  21.     if(lr <= l && r <= rr){
  22.         all[v] = true;
  23.         a[v] = (r - l) * y;
  24.         return;
  25.     }
  26.     if(all[v])
  27.         push(v, l, r);
  28.     all[v] = false;
  29.     int m = (r+l)/2;
  30.     setx(v*2 +1, l, m, lr, rr, y);
  31.     setx(v*2 +2, m, r, lr, rr, y);
  32.     a[v] = a[v*2 + 1] + a[v*2 + 2];
  33. }
  34.  
  35. ll get(int v, int l, int r, int lr, int rr){
  36.     if(r <= lr || rr <= l)
  37.         return 0;
  38.     if(lr <= l && r <= rr)
  39.         return a[v];
  40.     if(all[v])
  41.         push(v, l, r);
  42.     int m = (r+l)/2;
  43.     return get(v*2+1, l, m, lr, rr) + get(v*2+2, m, r, lr, rr);
  44. }
  45.  
  46. int main() {
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(0);
  49.  
  50.     int n, m, t, l, r, v;
  51.     cin >> n >> m;
  52.     a.resize(4*n, 0);
  53.     all.resize(4*n, true);
  54.     while(m--){
  55.         cin >> t >> l >> r;
  56.         if(t == 1){
  57.             cin >> v;
  58.             setx(0, 0, n, l, r, v);
  59.         } else{
  60.             cout << get(0, 0, n, l, r) << endl;
  61.         }
  62.     }
  63.  
  64.  
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement