Advertisement
oleg_drawer

do struct [set_segm, get_segm]

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