原题链接

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100005]={0};
ll lazyadd[400005]={0};
ll lazymul[400005]={0};
ll tree[400005]={0};
ll n,q,m;

void build(ll node, ll start, ll end)
{
    lazyadd[node]=0;
    lazymul[node]=1;

    if(start!=end)
    {
        ll mid=(start+end)/2;
        build(node*2,start,mid);
        build(node*2+1,mid+1,end);
        tree[node]=(tree[2*node+1]+tree[2*node])%m;
    }
    else tree[node]=a[start]%m;
}

void updatemul(ll node, ll start, ll end, ll l, ll r, ll val)
{
    if(lazyadd[node]!=0||lazymul[node]!=1)//lazy代表当前节点要加或乘的数量
    {
        tree[node]=(lazymul[node]*tree[node]%m+(end-start+1)*lazyadd[node]%m)%m;//每更新一个mul都会更新一次add所以add已经被后来的mul乘过了，可以直接加
        if(start!=end)
        {
            lazymul[node*2]=lazymul[node*2]*lazymul[node]%m;//每一个mul都是新的，不会出现 重复的情况
            lazyadd[node*2]=(lazyadd[node*2]*lazymul[node]+lazyadd[node])%m;//每传递一个mul都要给被传递节点的现在值tree和待加值add乘上
            lazymul[node*2+1]=lazymul[node*2+1]*lazymul[node]%m;
            lazyadd[node*2+1]=(lazyadd[node*2+1]*lazymul[node]+lazyadd[node])%m;
        }
        lazymul[node]=1;
        lazyadd[node]=0;
    }
    if(r<start||l>end) return;

    if(start>=l&&end<=r)//如果是最外面的完全包裹区间
    {
        tree[node]=tree[node]*val%m;
        if(start!=end)
        {
            lazyadd[node*2]=lazyadd[node*2]*val%m;
            lazymul[node*2]=lazymul[node*2]*val%m;
            lazyadd[node*2+1]=lazyadd[node*2+1]*val%m;
            lazymul[node*2+1]=lazymul[node*2+1]*val%m;
        }
        return;
    }

    ll mid=(start+end)/2;
    updatemul(node*2,start,mid,l,r,val);
    updatemul(node*2+1,mid+1,end,l,r,val);
    tree[node]=(tree[node*2]+tree[node*2+1])%m;//这个区间的值并不是全部修改
}

void updateadd(ll node, ll start, ll end, ll l, ll r, ll val)
{
    if(lazyadd[node]!=0||lazymul[node]!=1)
    {
        tree[node]=(lazymul[node]*tree[node]%m+(end-start+1)*lazyadd[node]%m)%m;
        if(start!=end)
        {
            lazymul[node*2]=lazymul[node*2]*lazymul[node]%m;
            lazyadd[node*2]=(lazyadd[node*2]*lazymul[node]+lazyadd[node])%m;
            lazymul[node*2+1]=lazymul[node*2+1]*lazymul[node]%m;
            lazyadd[node*2+1]=(lazyadd[node*2+1]*lazymul[node]+lazyadd[node])%m;
        }
        lazymul[node]=1;
        lazyadd[node]=0;
    }
    if(r<start||l>end) return;

    if(start>=l&&end<=r)
    {
        tree[node]=(tree[node]+val*(end-start+1))%m;
        if(start!=end)
        {
            lazyadd[node*2]+=val;
            lazyadd[node*2+1]+=val;
        }
        return;
    }

    ll mid=(start+end)/2;
    updateadd(node*2,start,mid,l,r,val);
    updateadd(node*2+1,mid+1,end,l,r,val);
    tree[node]=(tree[node*2]+tree[node*2+1])%m;
}

ll query(ll node, ll start, ll end, ll l, ll r)
{
    if(r<start||l>end) return 0;
    if(lazyadd[node]!=0||lazymul[node]!=1)
    {
        tree[node]=(lazymul[node]*tree[node]%m+(end-start+1)*lazyadd[node]%m)%m;
        if(start!=end)
        {
            lazymul[node*2]=lazymul[node*2]*lazymul[node]%m;
            lazyadd[node*2]=(lazyadd[node*2]*lazymul[node]+lazyadd[node])%m;
            lazymul[node*2+1]=lazymul[node*2+1]*lazymul[node]%m;
            lazyadd[node*2+1]=(lazyadd[node*2+1]*lazymul[node]+lazyadd[node])%m;
        }
        lazymul[node]=1;
        lazyadd[node]=0;
    }

    if(start>=l&&end<=r) return tree[node]%m;
    else
    {
        ll mid=(start+end)/2;
        return (query(node*2,start,mid,l,r)+query(node*2+1,mid+1,end,l,r))%m;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q >> m;
    for(ll i=1; i<=n; i++) cin >> a[i];
    build(1,1,n);
    while(q--)
    {
        ll op,x,y,k;
        cin >> op;
        if(op==1)
        {
            cin >> x >> y >> k;
            updatemul(1,1,n,x,y,k);
        }
        else if(op==2)
        {
            cin >> x >> y >> k;
            updateadd(1,1,n,x,y,k);
        }
        else
        {
            cin >> x >> y;
            cout << query(1,1,n,x,y) << endl;
        }
    }
    return 0;
}