Advertisement
oleg_drawer

do array fast cin/cout [set_segm, get_segm]

Jun 3rd, 2020
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.59 KB | None | 0 0
  1. //  do array fast cin/cout [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<<1) + 1] = true;
  11.     all[(v<<1) + 2] = true;
  12.     ll y = a[v] / (r-l);
  13.     int m = (r+l)>>1;
  14.     a[(v<<1) +1] = y* (m - l);
  15.     a[(v<<1) +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<<1) +1, l, m, lr, rr, y);
  31.     setx((v<<1) +2, m, r, lr, rr, y);
  32.     a[v] = a[(v<<1) + 1] + a[(v<<1) + 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)>>1;
  43.     return get((v<<1)+1, l, m, lr, rr) + get((v<<1)+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(n<<2, 0);
  53.     all.resize(n<<2, true);
  54.     vector<ll> ans(0);
  55.     int q[m][4];
  56.     for(int i = 0; i < m; i++){
  57.         cin >> q[i][0] >> q[i][1] >> q[i][2];
  58.         if(q[i][0] == 1)//{
  59.             cin >> q[i][3];
  60.     }
  61.     for(auto i: q){
  62.         if(i[0] == 1)//{
  63.             setx(0, 0, n, i[1], i[2], i[3]);
  64.         else
  65.             ans.push_back(get(0, 0, n, i[1], i[2]));
  66.     }
  67.     for(auto i: ans)
  68.         cout << i << endl;
  69.  
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement