#include<cstdio>
#define ll long long
#define N 100005
using namespace std;
int n,q,m;
ll w[N*4],tagadd[N*4],tagmul[N*4],a[N];
void pushup(int u){
    w[u]=(w[u*2]+w[u*2+1])%m;
}
void build(int u,int l,int r){
    if(l==r){
        w[u]=a[l]%m;
        return;
    }
    int mid=(l+r)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
    tagmul[u]=1;
}
void maketag(int u,int len,ll x,int type){//1:mul,2:add
    if(type==1){
        tagadd[u]=(tagadd[u]*x)%m;
        tagmul[u]=(tagmul[u]*x)%m;
        w[u]=(w[u]*x)%m;
    }
    else{
        tagadd[u]=(tagadd[u]+x)%m;
        w[u]=(w[u]+len*x%m)%m;
    }
}
void pushdown(int u,int l,int r){
    int mid=(l+r)/2;
    maketag(u*2,mid-l+1,tagmul[u],1);
    maketag(u*2,mid-l+1,tagadd[u],2);
    maketag(u*2+1,r-mid,tagmul[u],1);
    maketag(u*2+1,r-mid,tagadd[u],2);
    tagmul[u]=1;
    tagadd[u]=0;
}
inline bool inrange(int l,int r,int L,int R){
    return(L<=l&&r<=R);
}
inline bool outofrange(int l,int r,int L,int R){
    return(l>R||r<L);
}
ll query(int u,int l,int r,int L,int R){
    if(inrange(l,r,L,R)) return w[u];
    else if(!outofrange(l,r,L,R)){
        int mid=(l+r)/2;
        pushdown(u,l,r);
        return (query(u*2,l,mid,L,R)+query(u*2+1,mid+1,r,L,R))%m;
    }
    else return 0;
}
void update(int u,int l,int r,int L,int R,ll x,int type){
    if(inrange(l,r,L,R)) maketag(u,r-l+1,x,type);
    else if(!outofrange(l,r,L,R)){
        int mid=(l+r)/2;
        pushdown(u,l,r);
        update(u*2,l,mid,L,R,x,type);
        update(u*2+1,mid+1,r,L,R,x,type);
        pushup(u);
    }
}
int main(){
    scanf("%d%d%d",&n,&q,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        int type,x,y,k;
        scanf("%d%d%d",&type,&x,&y);
        if(type==1||type==2){
            scanf("%d",&k);
            update(1,1,n,x,y,k,type);
        }
        else{
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

m用变量1.37s

#include<cstdio>
#define ll long long
#define N 100005
using namespace std;
int n,q,p;
const int m=571373;
ll w[N*4],tagadd[N*4],tagmul[N*4],a[N];
void pushup(int u){
    w[u]=(w[u*2]+w[u*2+1])%m;
}
void build(int u,int l,int r){
    if(l==r){
        w[u]=a[l]%m;
        return;
    }
    int mid=(l+r)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    pushup(u);
    tagmul[u]=1;
}
void maketag(int u,int len,ll x,int type){//1:mul,2:add
    if(type==1){
        tagadd[u]=(tagadd[u]*x)%m;
        tagmul[u]=(tagmul[u]*x)%m;
        w[u]=(w[u]*x)%m;
    }
    else{
        tagadd[u]=(tagadd[u]+x)%m;
        w[u]=(w[u]+len*x%m)%m;
    }
}
void pushdown(int u,int l,int r){
    int mid=(l+r)/2;
    maketag(u*2,mid-l+1,tagmul[u],1);
    maketag(u*2,mid-l+1,tagadd[u],2);
    maketag(u*2+1,r-mid,tagmul[u],1);
    maketag(u*2+1,r-mid,tagadd[u],2);
    tagmul[u]=1;
    tagadd[u]=0;
}
inline bool inrange(int l,int r,int L,int R){
    return(L<=l&&r<=R);
}
inline bool outofrange(int l,int r,int L,int R){
    return(l>R||r<L);
}
ll query(int u,int l,int r,int L,int R){
    if(inrange(l,r,L,R)) return w[u];
    else if(!outofrange(l,r,L,R)){
        int mid=(l+r)/2;
        pushdown(u,l,r);
        return (query(u*2,l,mid,L,R)+query(u*2+1,mid+1,r,L,R))%m;
    }
    else return 0;
}
void update(int u,int l,int r,int L,int R,ll x,int type){
    if(inrange(l,r,L,R)) maketag(u,r-l+1,x,type);
    else if(!outofrange(l,r,L,R)){
        int mid=(l+r)/2;
        pushdown(u,l,r);
        update(u*2,l,mid,L,R,x,type);
        update(u*2+1,mid+1,r,L,R,x,type);
        pushup(u);
    }
}
int main(){
    scanf("%d%d%d",&n,&q,&p);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        int type,x,y,k;
        scanf("%d%d%d",&type,&x,&y);
        if(type==1||type==2){
            scanf("%d",&k);
            update(1,1,n,x,y,k,type);
        }
        else{
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

const int m 498ms

总结：模数用常量比变量快