【线段树区间乘】线段树2

Love The Way You Lie 2024-03-25 21:10 7阅读 0赞

**说是应用，其实也算是模板吧**

[P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P3373 _ 2 - _ _ _ _luogu.com.cn]

题意：

![bf023feefa023a1dcaf7c9bdf324643c.png][]

思路：

加个mul tag就好了

就当作板子好了

Code：

/*
    线段树tag：记录每个数的变化情况
    add:区间中每个数的增加值
    mul:区间中每个数需要乘的数
    在pushdown的过程中不断更新tag
    */
    #include <bits/stdc++.h>
    #define int long long
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Mnf=1e18;
    const int Inf=-1e18;
    using namespace std;
    
    
    struct Tree{
        int val,add,mul;
    }tree[mxe<<2];
    
    
    int n,m,op,l,r,k,M;
    int a[mxn];
    void pushup(int rt){
        tree[rt].val=(tree[rt<<1].val+tree[rt<<1|1].val)%M;
    }
    
    void pushdown(int rt,int tot){
        tree[rt<<1].val=((tot-tot/2)*tree[rt].add+tree[rt<<1].val*tree[rt].mul)%M;
        tree[rt<<1|1].val=(tree[rt<<1|1].val*tree[rt].mul+(tot/2)*tree[rt].add)%M;
    
        tree[rt<<1].mul=(tree[rt<<1].mul*tree[rt].mul)%M;
        tree[rt<<1|1].mul=(tree[rt<<1|1].mul*tree[rt].mul)%M;
    
        tree[rt<<1].add=((tree[rt<<1].add*tree[rt].mul)%M+tree[rt].add)%M;
        tree[rt<<1|1].add=((tree[rt<<1|1].add*tree[rt].mul)%M+tree[rt].add)%M;
    
        tree[rt].add=0;
        tree[rt].mul=1;
        //cout<<tot/2<<tree[rt].add<<tree[rt<<1|1].val<<tree[rt].mul<<'\n';
    }
    
    int query(int rt,int l,int r,int x,int y,Tree *tree){
        if(x<=l&&r<=y){
            return tree[rt].val;
        }
    
        pushdown(rt,r-l+1);
    
        int mid=l+r>>1;
        int res=0;
        if(x<=mid) res=(res+query(rt<<1,l,mid,x,y,tree))%M;
        if(y>mid) res=(res+query(rt<<1|1,mid+1,r,x,y,tree))%M;
        return res;
    }
    
    void modify_mul(int rt,int l,int r,int x,int y,int k,Tree *tree){
        if(x<=l&&r<=y){
            tree[rt].add=(tree[rt].add*k)%M;
            tree[rt].mul=(tree[rt].mul*k)%M;
            tree[rt].val=(tree[rt].val*k)%M;
            return;
        }
    
        pushdown(rt,r-l+1);
    
        int mid=l+r>>1;
        if(x<=mid) modify_mul(rt<<1,l,mid,x,y,k,tree);
        if(y>mid) modify_mul(rt<<1|1,mid+1,r,x,y,k,tree);
        pushup(rt);
    }
    void modify_sum(int rt,int l,int r,int x,int y,int k,Tree *tree){
        if(x<=l&&r<=y){
            tree[rt].add=(tree[rt].add+k)%M;
            tree[rt].val=(tree[rt].val+(r-l+1)*k)%M;
            return;
        }
    
        pushdown(rt,r-l+1);
    
        int mid=l+r>>1;
        int res=0;
        if(x<=mid) modify_sum(rt<<1,l,mid,x,y,k,tree);
        if(y>mid) modify_sum(rt<<1|1,mid+1,r,x,y,k,tree);
        pushup(rt); 
    }
    
    void build(int rt,int l,int r,Tree *tree){
        tree[rt].add=0;
        tree[rt].mul=1;
    
        if(l==r){
            tree[rt].val=a[l]%M;
            return;
        }
    
        int mid=l+r>>1;
        build(rt<<1,l,mid,tree);
        build(rt<<1|1,mid+1,r,tree);
        pushup(rt);
    }
    
    void solve(){
        cin>>n>>m>>M;
        for(int i=1;i<=n;i++) cin>>a[i];
        build(1,1,n,tree);
        for(int i=1;i<=m;i++){
            cin>>op;
            if(op==1){
                cin>>l>>r>>k;
                modify_mul(1,1,n,l,r,k,tree);
            }else if(op==2){
                cin>>l>>r>>k;
                modify_sum(1,1,n,l,r,k,tree);
            }else{
                cin>>l>>r;
                cout<<query(1,1,n,l,r,tree)%M<<'\n';
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[P3373 _ 2 - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P3373
[bf023feefa023a1dcaf7c9bdf324643c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5807f29746f4439bb89e94afb35ddf3d.png