Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define nl "\n"
- #define fi first
- #define se second
- #define pb push_back
- #define ll long long
- #define RV return void
- #define sz(x) int(x.size())
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- const ll mod = 1e9 + 7;
- struct Node{
- ll sum, lazy;
- bool is_lazy;
- Node(ll x = 0 ){
- sum = x;
- lazy = 1;
- is_lazy = false;
- }
- void change(ll x){
- sum = ((sum % mod) * (x % mod)) % mod;
- lazy = ((lazy % mod) * (x % mod)) % mod;
- is_lazy = true;
- }
- };
- struct LazyPropagation{
- int tree_size;
- vector<Node> tree;
- LazyPropagation(int n){
- tree_size = 1;
- while (tree_size < n) tree_size *= 2;
- tree.assign(2 * tree_size, Node(1));
- }
- Node merge(Node &left, Node &right){
- Node ans = Node();
- ans.sum = (left.sum % mod + right.sum % mod ) % mod;
- return ans;
- }
- void propagate(int node, int lx, int rx){
- if(!tree[node].is_lazy or rx - lx == 1)
- return ;
- int md = lx + (rx - lx) / 2;
- tree[2 * node + 1].change(tree[node].lazy);
- tree[2 * node + 2].change(tree[node].lazy);
- tree[node].lazy = 1;
- tree[node].is_lazy = false;
- }
- void set(int l, int r, ll val, int node, int lx, int rx){
- propagate(node, lx, rx);
- if(lx >= l and rx <= r){
- tree[node].change(val);
- return ;
- }
- if(lx >= r or rx <= l)
- return ;
- int md = lx + (rx - lx) / 2;
- set(l, r, val, 2 * node + 1, lx, md);
- set(l, r, val, 2 * node + 2, md, rx);
- tree[node] = merge(tree[2 * node + 1], tree[2 * node + 2]);
- }
- void set(int l, int r, ll val){
- set(l, r, val, 0, 0, tree_size);
- }
- Node get(int l, int r, int node, int lx, int rx){
- propagate(node, lx, rx);
- if(lx >= l and rx <= r)
- return tree[node];
- if(lx >= r or rx <= l)
- return Node();
- int md = lx + (rx - lx) / 2;
- Node left = get(l, r, 2 * node + 1, lx, md);
- Node right = get(l, r, 2 * node + 2, md, rx);
- return merge(left, right);
- }
- Node get(int l, int r){
- return get(l, r, 0, 0, tree_size);
- }
- };
- void solve(){
- int n,q; cin >> n >> q;
- LazyPropagation seg(n);
- while(q--){
- int op,l,r; cin >> op >> l >> r;
- if(op==1){
- ll val ; cin >> val;
- seg.set(l,r,val);
- }else{
- cout << seg.get(l,r).sum << nl;
- }
- }
- }
- int main(){
- ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
- int t=1;
- // cin >> t ;
- for(int i=1 ; i <= t ; i++){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement