先乘后加，懒标记更好维护（线段树）

P3373 【模板】线段树 2

当乘法和加法标记同时存在时，pushdown中传递懒标记时，先传乘标记，后传加标记更好维护  

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
ll n,m,mod;
ll a[N];
ll tree[N<<2];
struct L{
    ll a,b;  //a是*标记，b是+标记    //a为子树待加的数，b为子树待乘的数
    void _mod(int mod){
        a%=mod;b%=mod;
    }
}ly[N<<2];
void bulid(int p,int l,int r){
    ly[p].a =1;
    if(l==r){ tree[p]=a[l]%mod;return ;}
    int mid=(l+r)>>1;
    bulid(p*2,l,mid);
    bulid(p*2+1,mid+1,r);
    tree[p]=(tree[p*2]%mod+tree[p*2+1]%mod)%mod;
}
void pushdown(int p,int len){
    tree[p*2]=(tree[p*2]*ly[p].a%mod +(ly[p].b *(len-len/2)%mod))%mod;
    tree[p*2+1]=(tree[p*2+1]*ly[p].a%mod +(ly[p].b *(len/2))%mod)%mod;
    ly[p*2].a =(ly[p*2].a%mod *ly[p].a%mod)%mod ;        
    ly[p*2+1].a =(ly[p*2+1].a%mod *ly[p].a%mod)%mod ;    //以后可以用mu表示*标记
    ly[p*2].b =(ly[p*2].b*ly[p].a%mod  + ly[p].b%mod)%mod ;       //重点
    ly[p*2+1].b =(ly[p*2+1].b*ly[p].a%mod  + ly[p].b%mod)%mod ;    //
    ly[p].a =1;ly[p].b =0;
}
void change1(int p,int l,int r,int x,int y,int k){   //乘法维护
    if(x<=l&&r<=y){
        tree[p]=(tree[p]%mod * k%mod)%mod;
        ly[p].b=(ly[p].b%mod*k%mod)%mod;   //原先待加的数要乘上新来的乘数k
        ly[p].a=(ly[p].a%mod*k%mod)%mod;
        return ;
    }
    if(ly[p].a!=1 || ly[p].b ) pushdown(p,r-l+1);
    int mid=(l+r) >> 1;
    if(x<=mid) change1(p*2,l,mid,x,y,k);
    if(y>=mid+1) change1(p*2+1,mid+1,r,x,y,k);
    tree[p]=(tree[p*2]%mod+tree[p*2+1]%mod)%mod;
}
void change2(int p,int l,int r,int x,int y,int k){   //加法维护
    if(x<=l&&r<=y){
        tree[p]=(tree[p]%mod+(r-l+1)*k%mod)%mod;
        ly[p].b =(ly[p].b%mod +k%mod)%mod;
        return ;
    }
    if(ly[p].a!=1 || ly[p].b ) pushdown(p,r-l+1);
    int mid=(l+r) >> 1;
    if(x<=mid) change2(p*2,l,mid,x,y,k);
    if(mid+1<=y) change2(p*2+1,mid+1,r,x,y,k);
    tree[p]=(tree[p*2]%mod+tree[p*2+1]%mod)%mod;
}
ll ask(int p,int l,int r,int x,int y){  //询问区间和，所以不用改tree 
    if(x<=l&&r<=y){    return tree[p]%=mod;    }
    if(ly[p].a!=1 || ly[p].b ) pushdown(p,r-l+1); 
    int mid=(l+r) >> 1;
    ll res=0;
    if(x<=mid) res=(res%mod+ask(p*2,l,mid,x,y)%mod)%mod;
    if(mid+1<=y) res=(res%mod+ask(p*2+1,mid+1,r,x,y)%mod)%mod;
    return res%=mod;
}
int main(){
    cin >> n >> m >> mod;
    for(int i=1;i<=n;++i){
        cin >> a[i];
    }
    bulid(1,1,n);
    while(m--){
        int op,x,y,k;
        cin >> op >> x >> y;
        if(op==1){
            cin >> k;
            change1(1,1,n,x,y,k);
        }
        else if(op==2){
            cin >> k;
            change2(1,1,n,x,y,k);
        }
        else{
            cout << ask(1,1,n,x,y)%mod << "\n";  //cout << endl;输出一次endl就要清空缓存，比较慢  //cout << "\n"快一点 
        }    
    }
    return 0; 
}