我不会线段树...求

P3373
#include <bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)

using namespace std;

const int N=1e5+23;
const int SN=4e5+23;
int n,q,mod;

int a[N],add[SN],mul[SN],sum[SN];

void push_up(int s,int t,int p)
{sum[p]=sum[p*2]+sum[p*2+1];sum[p]%=mod;}

void push_down(int s,int t,int p)
{
    int lc=p*2,rc=2*p+1,mid=s+(t-s)/2;
    if(mul[p]!=1)
    {
        mul[lc]*=mul[p];
        mul[lc]%=mod;
        mul[rc]*=mul[p];
        mul[rc]%=mod;
        add[lc]*=mul[p];
        add[lc]%=mod;
        add[rc]*=mul[p];
        add[rc]%=mod;
        sum[lc]*=mul[p];
        sum[lc]%=mod;
        sum[rc]*=mul[p];
        sum[rc]%=mod;
        mul[p]=1;
    }
    if(add[p]){
        sum[lc]+=add[p]*(mid-s+1);
        sum[lc]%=mod;
        sum[rc]+=add[p]*(t-mid);
        sum[rc]%=mod;
        add[lc]+=add[p];
        add[lc]%=mod;
        add[rc]+=add[p];
        add[rc]%=mod;
        add[p]=0;
    }
    return;
}

void build(int s,int t,int p)
{
    int lc=2*p,rc=2*p+1;
    if(s==t){
        sum[p]=a[s];return;
    }
    int mid=s+(t-s)/2;
    build(s,mid,lc);
    build(mid+1,t,rc);
    push_up(s,t,p);
}

void update_mul(int l,int r,int v,int s,int t,int p)
{
    int lc=2*p,rc=2*p+1;
    if(l<=s&&t<=r)
    {
        mul[p]*=v;
        mul[p]%=mod;
        add[p]*=v;
        add[p]%=mod;
        sum[p]*=v;
        sum[p]%=mod;
        return;
    }
    push_down(s,t,p);
    int mid=s+(t-s)/2;
    if(l<=mid)
        update_mul(l,r,v,s,mid,lc);
    if(r>mid)
        update_mul(l,r,v,mid+1,t,rc);
    push_up(s,t,p);
}

void update_add(int l,int r,int v,int s,int t,int p)
{
    int lc=2*p,rc=2*p+1;
    if(l<=s&&t<=r)
    {
        sum[p]+=v*(t-s+1);
        sum[p]%=mod;
        add[p]+=v;
        add[p]%=mod;
        return;
    }
    push_down(s,t,p);
    int mid=s+(t-s)/2;
    if(l<=mid)
        update_add(l,r,v,s,mid,lc);
    if(r>mid)
        update_add(l,r,v,mid+1,t,rc);
    push_up(s,t,p);
}

int query(int l,int r,int s,int t,int p)
{
    int lc=2*p,rc=2*p+1;
    if(l<=s&&t<=r)
        return sum[p];
    push_down(s,t,p);
    int tot=0,mid=s+(t-s)/2;
    if(l<=mid)
        tot+=query(l,r,s,mid,lc);
    tot%=mod;
    if(r>mid)
        tot+=query(l,r,mid+1,t,rc);
    tot%=mod;
    return tot;
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>q>>mod;
    rep(i,1,n)
        cin>>a[i];
    rep(i,1,q){
        int opt,x,y;
        cin>>opt>>x>>y;
        if(opt==1){
            int k;
            cin>>k;
            update_mul(x,y,k,1,n,1);
        }
        if(opt==2){
            int k;
            cin>>k;
            update_add(x,y,k,1,n,1);
        }
        if(opt==3)
            cout<<query(x,y,1,n,1)<<endl;
    }
}