Advertisement
Zeinab_Hamdy

Untitled

Dec 25th, 2024
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define nl "\n"
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. #define ll long long
  8. #define RV return void
  9. #define sz(x) int(x.size())
  10. #define all(v) v.begin(), v.end()
  11. #define rall(v) v.rbegin(), v.rend()
  12.  
  13.  
  14. const ll mod = 1e9 + 7;
  15. struct Node{
  16.     ll sum, lazy;
  17.     bool is_lazy;
  18.  
  19.     Node(ll x = 0 ){
  20.         sum = x;
  21.         lazy = 1;
  22.         is_lazy = false;
  23.     }
  24.     void change(ll x){
  25.         sum = ((sum % mod) * (x % mod)) % mod;
  26.         lazy = ((lazy % mod) * (x % mod)) % mod;
  27.         is_lazy = true;
  28.     }
  29. };
  30.  
  31. struct LazyPropagation{
  32.     int tree_size;
  33.     vector<Node> tree;
  34.  
  35.     LazyPropagation(int n){
  36.         tree_size = 1;
  37.         while (tree_size < n) tree_size *= 2;
  38.         tree.assign(2 * tree_size, Node(1));
  39.     }
  40.  
  41.     Node merge(Node &left, Node &right){
  42.         Node ans = Node();
  43.         ans.sum = (left.sum % mod + right.sum % mod ) % mod;
  44.         return ans;
  45.     }
  46.  
  47.     void propagate(int node, int lx, int rx){
  48.         if(!tree[node].is_lazy or rx - lx == 1)
  49.             return ;
  50.  
  51.         int md = lx + (rx - lx) / 2;
  52.         tree[2 * node + 1].change(tree[node].lazy);
  53.         tree[2 * node + 2].change(tree[node].lazy);
  54.  
  55.         tree[node].lazy = 1;
  56.         tree[node].is_lazy = false;
  57.     }
  58.  
  59.     void set(int l, int r, ll val, int node, int lx, int rx){
  60.         propagate(node, lx, rx);
  61.         if(lx >= l and rx <= r){
  62.             tree[node].change(val);
  63.             return ;
  64.         }
  65.  
  66.         if(lx >= r or rx <= l)
  67.             return ;
  68.  
  69.         int md = lx + (rx - lx) / 2;
  70.         set(l, r, val, 2 * node + 1, lx, md);
  71.         set(l, r, val, 2 * node + 2, md, rx);
  72.  
  73.         tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);
  74.     }
  75.  
  76.     void set(int l, int r, ll val){
  77.         set(l, r, val, 0, 0, tree_size);
  78.     }
  79.  
  80.     Node get(int l, int r, int node, int lx, int rx){
  81.         propagate(node, lx, rx);
  82.         if(lx >= l and rx <= r)
  83.             return tree[node];
  84.         if(lx >= r or rx <= l)
  85.             return Node();
  86.  
  87.         int md = lx + (rx - lx) / 2;
  88.  
  89.         Node left = get(l, r, 2 * node + 1, lx, md);
  90.         Node right = get(l, r, 2 * node + 2, md, rx);
  91.  
  92.         return merge(left, right);
  93.     }
  94.  
  95.     Node get(int l, int r){
  96.         return get(l, r, 0, 0, tree_size);
  97.     }
  98. };
  99.  
  100.  
  101. void solve(){
  102.  
  103.  
  104.     int n,q; cin >> n >> q;
  105.  
  106.     LazyPropagation seg(n);
  107.     while(q--){
  108.         int op,l,r; cin >> op >> l >> r;
  109.         if(op==1){
  110.             ll val ; cin >> val;
  111.             seg.set(l,r,val);
  112.         }else{
  113.             cout << seg.get(l,r).sum << nl;
  114.         }
  115.     }
  116.    
  117. }
  118.  
  119.  
  120. int main(){
  121.     ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);  
  122.     int t=1;
  123.         // cin >> t ;
  124.     for(int i=1 ; i <= t ; i++){
  125.         solve();
  126.     }
  127.     return 0;
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement