题解 P3373 【【模板】线段树 2】

· · 题解

我来发一个C++题解吧，

也是受了p党题解的启发，用了两个lazy标记各存加法和乘法结果

大家可能觉得pushdown()部分过于冗长，但是事实上%p为了防炸，而且lazy1,lazy2更新时，都需要调用爸爸节点的lazy1,lazy2，所以不能写成单独的加法更新和乘法更新，不然会WA（不要问我怎么知道的）。

然而建议把加法修改和乘法修改分开写以提高效率。

最后一条——

_不要试图提交本题解所提供的代码，除非您是玄学大佬（误），否则极有可能会T掉最后三个点（不要问我怎么知道的）_

//%std
#include<bits/stdc++.h>
using namespace std;

int n,m,p;

long long a[500200],f[500200];

struct tree
{
    long long l,r,sum,lazy1,lazy2;
} t[500200];

void buildtree(int l,int r,int i)
{
    int zuo=i<<1;
    t[i].l=l;
    t[i].r=r;
    t[i].lazy1=0;
    t[i].lazy2=1;
    if(l==r)
        t[i].sum=a[l];
    else
    {
        int mid=(l+r)>>1;
        buildtree(l,mid,zuo);
        buildtree(mid+1,r,zuo|1);
        t[i].sum=t[zuo].sum+t[zuo|1].sum;
    }
    return;
}

void pushdown(int i)
{
    int zuo=i<<1;
    if(t[i].lazy1==0&&t[i].lazy2==1)    return;
    if(t[i].l==t[i].r)
    {
        t[i].lazy2=1;
        t[i].lazy1=0;
        return;
    }
    t[zuo].sum=(t[zuo].sum*t[i].lazy2+t[i].lazy1*(t[zuo].r-t[zuo].l+1))%p;
    t[zuo|1].sum=(t[zuo|1].sum*t[i].lazy2+t[i].lazy1*(t[zuo|1].r-t[zuo|1].l+1))%p;
    t[zuo].lazy2=t[zuo].lazy2*t[i].lazy2%p;
    t[zuo].lazy1=(t[zuo].lazy1*t[i].lazy2+t[i].lazy1)%p;
    t[zuo|1].lazy2=t[zuo|1].lazy2*t[i].lazy2%p;
    t[zuo|1].lazy1=(t[zuo|1].lazy1*t[i].lazy2+t[i].lazy1)%p;
    t[i].lazy2=1;
    t[i].lazy1=0;
    return;
}

void xiu_1(int i,int l,int r,long long add)
{
    pushdown(i);
    int zuo=i<<1;
    if(l<=t[i].l&&r>=t[i].r)
    {
        t[i].sum+=(t[i].r-t[i].l+1)*add%p;
        t[i].lazy1=add%p;
        return;
    }
    if(l>t[i].r||r<t[i].l)
        return;
    xiu_1(zuo,l,r,add);
    xiu_1(zuo|1,l,r,add);
    t[i].sum=(t[zuo].sum+t[zuo|1].sum)%p;
    return;
}

void xiu_2(int i,int l,int r,long long add)
{
    int zuo=i<<1;
    pushdown(i);
    if(l<=t[i].l&&r>=t[i].r)
    {
        t[i].sum=t[i].sum*add%p;
        t[i].lazy2=add%p;
        return;
    }
    if(l>t[i].r||r<t[i].l)
        return;
    xiu_2(zuo,l,r,add);
    xiu_2(zuo|1,l,r,add);
    t[i].sum=(t[zuo].sum+t[zuo|1].sum)%p;
    return;
}

long long query(int i,int l,int r)
{
    int zuo=i<<1;
    if(l<=t[i].l&&r>=t[i].r)
        return t[i].sum;
    if(l>t[i].r||r<t[i].l)
        return 0;
    pushdown(i);
    return query(zuo,l,r)+query(zuo|1,l,r);
}

long long lread()
{
    long long f=1,n=0;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        n*=10;
        n+=c-'0';
        c=getchar();
    }
    return n*f;
}

int read()
{
    int f=1,n=0;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0')
    {
        n*=10;
        n+=c-'0';
        c=getchar();
    }
    return n*f;
}

int main()
{
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1; i<=n; i++)
        a[i]=lread();
    buildtree(1,n,1);
    for(int i=1; i<=m; i++)
    {
        int key;
        scanf("%d",&key);
        if(key==1)
        {
            int x=read(),y=read(),k=read();
            xiu_2(1,x,y,k);
        }
        else if(key==2)
        {
            int x=read(),y=read(),k=read();
            xiu_1(1,x,y,k);
        }
        else
        {
            int x=read(),y=read();
            printf("%d\n",query(1,x,y)%p);
        }
    }
    return 0;
}