链接：Miku

和[线段树2]（https://www.luogu.com.cn/problem/P3373）

一样的题

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long 
using namespace std;
int n,mod;
int tree[400001];
int lazya[400001],lazym[400001];
int m;
int sum[400001];
int f,t,g,c; 
void pushup(int x){
    sum[x]=sum[x<<1]%mod+sum[x<<1|1]%mod;
    sum[x]%=mod;
    return ; 
} 
void pushdown(int x,int l,int r){
    if(lazym[x]!=1){
        lazym[x<<1]*=lazym[x]%mod;lazym[x<<1|1]*=lazym[x]%mod;
        lazym[x<<1]%=mod;lazym[x<<1|1]%=mod;
        sum[x<<1]*=lazym[x]%mod;sum[x<<1|1]*=lazym[x]%mod;
        sum[x<<1]%=mod;sum[x<<1|1]%=mod;
        lazya[x<<1]*=lazym[x]%mod;lazya[x<<1|1]*=lazym[x]%mod;
        lazya[x<<1]%=mod;lazya[x<<1|1]%=mod;
        lazym[x]=1;
    }
    if(lazya[x]){
        int mid=(l+r)>>1;
        lazya[x<<1]+=lazya[x]%mod;lazya[x<<1|1]+=lazya[x]%mod;
        sum[x<<1]+=lazya[x]*(mid-l+1);
        sum[x<<1]%=mod;
        sum[x<<1|1]+=lazya[x]*(r-mid);
        sum[x<<1|1]%=mod;
        lazya[x<<1]%=mod;lazya[x<<1|1]%=mod;
        lazya[x]=0;
    }
    return ;
}
void update1(int x,int l,int r,int L,int R,int ad){
    if(L<=l&&r<=R){
        lazya[x]+=ad;
        lazya[x]%=mod;
        sum[x]+=(r-l+1)*ad;
        sum[x]%=mod;
        return ; 
    }
    pushdown(x,l,r);
    int mid=(r+l)>>1;
    if(L<=mid) update1(x<<1,l,mid,L,R,ad);
    if(R>mid) update1(x<<1|1,mid+1,r,L,R,ad);
    pushup(x);
    return ;    
}
void update2(int x,int l,int r,int L,int R,int ad){
    if(L<=l&&r<=R){
        lazym[x]*=ad;
        lazym[x]%=mod;
        lazya[x]*=ad;
        lazya[x]%=mod;
        sum[x]*=ad;
        sum[x]%=mod;
        return ; 
    }
    pushdown(x,l,r);
    int mid=(r+l)>>1;
    if(L<=mid) update2(x<<1,l,mid,L,R,ad);
    if(R>mid) update2(x<<1|1,mid+1,r,L,R,ad);
    pushup(x);
    return ;    
}
int query(int x,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return sum[x]%=mod;
    }
    pushdown(x,l,r);
    int mid=(r+l)>>1;
    int ans=0;
    if(L<=mid) ans+=query(x<<1,l,mid,L,R),ans%=mod;
    if(R>mid) ans+=query(x<<1|1,mid+1,r,L,R),ans%=mod;
    return ans%=mod;
} 
signed main(){
    scanf("%lld%lld",&n,&mod);
    for(int i=1;i<=400001;++i)
    lazym[i]=1;
    for(int i=1;i<=n;++i){
        scanf("%lld",&m);
        update1(1,1,n,i,i,m);
    }
    scanf("%lld",&m);
    for(int i=1;i<=m;++i){
        scanf("%lld",&f);
        if(f==2){
            scanf("%lld%lld%lld",&t,&g,&c);
            update1(1,1,n,t,g,c);
        }
        if(f==1){
            scanf("%lld%lld%lld",&t,&g,&c);
            update2(1,1,n,t,g,c);
        }
        if(f==3){
            scanf("%lld%lld",&t,&g);
            cout<<query(1,1,n,t,g)%mod<<endl;;
        }
    } 
    return 0;
}