悬赏5RMB求调线段树(30分)

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long int ll;
ll n,m,mod,opt;
long long a[maxn],w[maxn*4];
long long add[maxn*4],mu[maxn*4]; //加法和乘法的lazy标记 
void pushop(ll u){ //计算当前节点的和 
    w[u*2]%=mod;
    w[u*2+1]%=mod;
    w[u]=w[u*2]+w[u*2+1]; 
    w[u]%=mod;
}
void build(ll u,ll L,ll R){ //建树 
    add[u]=0;
    mu[u]=1;
    if(L==R){
        w[u]=a[L];
        w[u]%=mod;
        return;
    }
    ll mid=(L+R)/2;
    build(u*2,L,mid);
    build(u*2+1,mid+1,R);
    pushop(u);
}
void maketag(ll u,ll L,ll R,long long x,long long y){ //+x,*y
    if(y!=0) w[u]=1ll*w[u]*y%mod;
    w[u]=(w[u]+1ll*x*(R-L+1))%mod;
    if(y!=0){
    	mu[u]=mu[u]*y%mod;
        add[u]=1ll*add[u]*y%mod;
    }
    add[u]=(add[u]+x)%mod;
}
void pushdown(ll u,ll L,ll R){
    ll mid=(L+R)/2;
    maketag(u*2,L,mid,add[u],mu[u]);
    maketag(u*2+1,mid+1,R,add[u],mu[u]);
    add[u]=0;
    mu[u]=1;
}
bool OutofRange(ll L,ll R,ll l,ll r){ //完全没有交集 
    return L>r||R<l;
}
bool InRange(ll L,ll R,ll l,ll r){ //完全包含 
    return L>=l&&R<=r;
}
long long query(ll u,ll L,ll R,ll l,ll r){
    if(OutofRange(L,R,l,r))return 0;
    if(InRange(L,R,l,r))return w[u]%mod;
    pushdown(u,L,R);
    ll mid=(L+R)/2;
    return (query(u*2,L,mid,l,r)%mod+query(u*2+1,mid+1,R,l,r)%mod)%mod;
}
void update_add(ll u,ll L,ll R,ll l,ll r,ll x){
    if(OutofRange(L,R,l,r))return;
    if(InRange(L,R,l,r)){
        maketag(u,L,R,x,0);
        return;
    }
    pushdown(u,L,R);
    ll mid=(L+R)/2;
    update_add(u*2,L,mid,l,r,x);
    update_add(u*2+1,mid+1,R,l,r,x);
    pushop(u);
}
void update_mu(ll u,ll L,ll R,ll l,ll r,ll x){
    if(OutofRange(L,R,l,r))return;
    if(InRange(L,R,l,r)){
        maketag(u,L,R,0,x);
        return;
    }
    pushdown(u,L,R);
    ll mid=(L+R)/2;
    update_mu(u*2,L,mid,l,r,x);
    update_mu(u*2+1,mid+1,R,l,r,x);
    pushop(u);
}
int main(){
    cin>>n>>m>>mod;
    for(ll i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    while(m--){
        ll x,y,k;
        cin>>opt;
        if(opt==1){
            cin>>x>>y>>k;
            update_mu(1,1,n,x,y,k);
        }
        if(opt==2){
            cin>>x>>y>>k;
            update_add(1,1,n,x,y,k);
        }
        if(opt==3){
            cin>>x>>y;
            cout<<query(1,1,n,x,y)%mod<<endl;
        }
    }
    return 0;
}
/*
5 10 100000
1 2 3 4 5
3 1 2
*/