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

· · 题解

大家都知道这是线段树

作为一道码农题，说几个注意事项

线段树之所以是O(nlogn)就是因为他有懒标记

这样的话，因为一个区间总是可以被拆分为logn个区间

所以操作都是logn的

那么在线段树上必须要有两个等式成立

1.懒标记结算后实际值=真实值

2.父节点真实值=子节点真实值之和

等式1不成问题，问题是如何维护等式2

在sum时是显然不行的，会由于不知道这个点的子树中是否有懒标记而导致非nlogn

所以一定是setlazy时了，具体来讲我们同时维护性质1和性质2

也就是说我们每次setlazy递归时更新父节点的值

另外由等式1可以解出来

(rval*rmult+rplus)*nmult+nplus=rval*amult+aplus

aplus=rplus*nmult+nplus;

amult=rmult*nmult;

其中r--表示子节点的值和懒标记

n--表示父节点的值和懒标记

a--表示pushdown后子节点的懒标记

还有就是这个版本的区间拆分还是比较亲民的

不用分情况讨论了

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;
int n;int m;int mod;
struct linetree
{
     long long val[400010];//必！须！开！long！long！
     long long lazp[400010];
     long long lazm[400010];
     inline void update(int p,int l,int r)
     {
         val[p]*=lazm[p];val[p]%=mod;val[p]+=lazp[p]*(r-l);val[p]%=mod;return;
        //更新节点值，先乘后加
     }
     inline void pushdown(int p,int l,int r)
     {
         update(p,l,r);//先更新 
         if(r-l>1)//非叶子节点
         {
             lazp[2*p]*=lazm[p];lazp[2*p]+=lazp[p];lazp[2*p]%=mod;//更新
             lazm[2*p]*=lazm[p];lazm[2*p]%=mod;
             lazp[2*p+1]*=lazm[p];lazp[2*p+1]+=lazp[p];lazp[2*p+1]%=mod;
             lazm[2*p+1]*=lazm[p];lazm[2*p+1]%=mod;
        }lazp[p]=0;lazm[p]=1;return;
     }
     int build(int p,int l,int r)//建树
     {
         lazm[p]=1;
         if(r-l==1)//如果是叶子
         {
             scanf("%lld",&val[p]);val[p]%=mod;return val[p];
        }
        int mid=(l+r)/2;
        if(mid>l)val[p]+=build(2*p,l,mid);
        if(mid<r)val[p]+=build(2*p+1,mid,r);
        val[p]%=mod;return val[p];
     }
     void setplus(int p,int l,int r,int dl,int dr,long long plus)//左端点，右端点，目标左，目标右
     {
         if(lazp[p]!=0||lazm[p]!=1)pushdown(p,l,r);
        //是这样的，因为你下面的点会回去更上来，
        //这样你的值就不准了，维护等式2的同时破坏了等式1
        //所以我们必须保证这个节点没有懒标记
         if(l==dl&&r==dr){lazp[p]+=plus;lazp[p]%=mod;pushdown(p,l,r);return;}
         int mid=(l+r)/2;
         if(mid>dl)setplus(2*p,l,mid,dl,min(mid,dr),plus);//无论如何必须保证孩子节点的值是准的
         else pushdown(2*p,l,mid);
         if(mid<dr)setplus(2*p+1,mid,r,max(mid,dl),dr,plus);
         else pushdown(2*p+1,mid,r);
         val[p]=val[2*p]+val[2*p+1];//回更，维护等式2
        return;
     }
     void setmult(int p,int l,int r,int dl,int dr,long long mult)//同上
     {
         if(lazm[p]!=1||lazp[p]!=0)pushdown(p,l,r); 
         if(l==dl&&r==dr)
        {lazp[p]*=mult;lazm[p]*=mult;lazp[p]%=mod;lazm[p]%=mod;pushdown(p,l,r);return;}
        int mid=(l+r)/2;
        if(mid>dl)setmult(2*p,l,mid,dl,min(mid,dr),mult);
        else pushdown(2*p,l,mid);
        if(mid<dr)setmult(2*p+1,mid,r,max(mid,dl),dr,mult);
        else pushdown(2*p+1,mid,r);
        val[p]=val[2*p]+val[2*p+1];
        return;
     }
     int sum(int p,int l,int r,int dl,int dr)//标准sum
     {
         if(lazp[p]!=0||lazm[p]!=1)pushdown(p,l,r);
         if(l==dl&&r==dr)return val[p];
         int mid=(l+r)/2;int res=0;
         if(mid>dl)res+=sum(2*p,l,mid,dl,min(mid,dr));//这个区间拆分可以避免分情况
         if(mid<dr)res+=sum(2*p+1,mid,r,max(mid,dl),dr);
         res%=mod;return res;
     }
}lt;
int main()
{
    scanf("%d%d%d",&n,&m,&mod);
    lt.build(1,0,n);
    for(int i=1;i<=m;i++)
    {
        int opt;int u;int v;
        scanf("%d%d%d",&opt,&u,&v);
        if(opt==1)
        {
            int t;scanf("%d",&t);
            lt.setmult(1,0,n,u-1,v,t);    
        }
        else if(opt==2)
        {
            int t;scanf("%d",&t);
            lt.setplus(1,0,n,u-1,v,t);
        }
        else if(opt==3)
        {
            printf("%d\n",lt.sum(1,0,n,u-1,v));
        }
    }return 0;//拜拜程序~
}