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

upd：9.28 补了一个锅 感谢@月离的提醒 # **这篇题解能帮助我什么？** １．这篇题解是**帮助大家理解先乘后加**的，很多人抄完题解就走啦并没有理解为什么要先乘后加。 ２．这篇题解的代码与线段树１十分相像，可以**帮助大家调试**。 3.(附加功能)本篇题解力求轻松幽默老少皆宜。 --- ## 前言: **所谓先乘后加就是在做乘法的时候把加法标记也乘上这个数，在后面做加法的时候直接加就行了。** ``` 先乘后加可(金)好(坷)啦(垃)好处都有啥?谁说对了就给他！ 先乘后加可(金)好(坷)啦(垃)，一题能顶两题啦！ 先乘后加可(金)好(坷)啦(垃)，NOIP一千八！ 先乘后加啦，时间不⽩撒；先加后乘呀，撒了也⽩搭 先乘后加可(金)好(坷)啦(垃)，不费时~！不怕Wa~！ 出题人，真不傻！时间给了他，对竞赛体验危害大，绝不能给他！ 线段树2毒(不)瘤(发)啊(达)，我们都要切(支)掉(援)他。先乘后加，毒(你)瘤(们)数(日)据(本)别~！想~！啦~！ ``` ## **锹黑板：** 首先我们回忆一下线段树１的加法标记**他其实是打在父亲节点上的标记儿子加多少的**，打完标记的同时父亲的sum其实已经加上了$add*len$ 那我们回到这道题我们发现题目要求在加数的同时**还要区间乘** 比如现在有3个数$1,2,3$ ``` 1~3(1) / \ 1~2(2) 3(3) / \ 1(4) 2(5) ``` **我们先给1~3加上2**,画个小小小小的图，**节点后面的括号代表节点下标** 所以 $t[1].add+=2;$ $t[1].sum+=((3-1)+1)*2;$ **我们再给1~3乘上3** 所以 $t[1].mu*=3;$ **我们再给1~3加上4，那是不是先加再乘** $t[1].add+=4;$ obviously我们发现不能先加： ``` 操作2之后的式子是: sum=(a[1]+2)*3+(a[2]+2)*3+(a[3]+2)*3; ``` 如果直接加: ``` 式子是: sum=(a[1]+2+4)*3+(a[2]+2+4)*3+(a[3]+2+4)*3; =(a[1]+2)*3+4*3+(a[2]+2)*3+4*3+(a[3]+2)*3+4*3; ``` 我们发现这和 ``` sum=(a[1]+2)*3+4+(a[2]+2)*3+4+(a[3]+2)*3+4; ``` 并不等价 而要等价必须这样 ``` sum=(a[1]+2+4/3)*3+(a[2]+2+4/3)*3+(a[3]+2+4/3)*3; ``` **我们发现这样就成了实数运算了,还有可能除成无限小数** 而先乘后加: ``` sum=(a[1]*3+2*3+4)+(a[2]*3+2*3+4)+(a[3]*3+2*3+4); ``` **嗯 老铁没毛病～～～** ## 给代码啦 ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; int n,m,a[1000005],mod; struct node{ ll sum,l,r,mu,add; }t[1000005]; ll read(){ ll x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; } void build(ll p,ll l,ll r){ t[p].l=l,t[p].r=r;t[p].mu=1; if(l==r){t[p].sum=a[l]%mod;return ;} ll mid=(l+r)>>1; build(p*2,l,mid); build(p*2+1,mid+1,r); t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod; } void spread(ll p){ t[p*2].sum=(ll)(t[p].mu*t[p*2].sum+((t[p*2].r-t[p*2].l+1)*t[p].add)%mod)%mod; t[p*2+1].sum=(ll)(t[p].mu*t[p*2+1].sum+(t[p].add*(t[p*2+1].r-t[p*2+1].l+1))%mod)%mod;//add已经乘过mu啦 t[p*2].mu=(ll)(t[p*2].mu*t[p].mu)%mod; t[p*2+1].mu=(ll)(t[p*2+1].mu*t[p].mu)%mod; t[p*2].add=(ll)(t[p*2].add*t[p].mu+t[p].add)%mod; t[p*2+1].add=(ll)(t[p*2+1].add*t[p].mu+t[p].add)%mod; t[p].mu=1,t[p].add=0; } void add(ll p,ll l,ll r,ll k){ if(t[p].l>=l&&t[p].r<=r){ t[p].add=(t[p].add+k)%mod; t[p].sum=(ll)(t[p].sum+k*(t[p].r-t[p].l+1))%mod;//只要加上增加的就好 return ; } spread(p); t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod; ll mid=(t[p].l+t[p].r)>>1; if(l<=mid)add(p*2,l,r,k); if(mid<r)add(p*2+1,l,r,k); t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod; } void mu(ll p,ll l,ll r,ll k){ if(t[p].l>=l&&t[p].r<=r){ t[p].add=(t[p].add*k)%mod;//比较重要的一步,add要在这里乘上k,因为后面可能要加其他的数而那些数其实是不用乘k的 t[p].mu=(t[p].mu*k)%mod; t[p].sum=(t[p].sum*k)%mod; return ; } spread(p); t[p].sum=t[p*2].sum+t[p*2+1].sum; ll mid=(t[p].l+t[p].r)>>1; if(l<=mid)mu(p*2,l,r,k); if(mid<r)mu(p*2+1,l,r,k); t[p].sum=(t[p*2].sum+t[p*2+1].sum)%mod; } ll ask(ll p,ll l,ll r){ if(t[p].l>=l&&t[p].r<=r){ return t[p].sum; } spread(p); ll val=0; ll mid=(t[p].l+t[p].r)>>1; if(l<=mid)val=(val+ask(p*2,l,r))%mod; if(mid<r)val=(val+ask(p*2+1,l,r))%mod; return val; } int main(){ cin>>n>>m>>mod; for(int i=1;i<=n;i++){ a[i]=read(); } build(1,1,n); for(int i=1;i<=m;i++){ int ty=read(); if(ty==1){ ll cn=read(),cm=read(),cw=read(); mu(1,cn,cm,cw); }else if(ty==2){ ll cn=read(),cm=read(),cw=read(); add(1,cn,cm,cw); }else { ll cn=read(),cm=read(); cout<<ask(1,cn,cm)<<endl; } } } ``` 更多资讯请进 **[BLOG](https://www.cnblogs.com/lqhsr)**