马上要进入暑假的训练了，所以复习了一下线段树的模板，感觉同最开始的理解又加深了一些，所以还是写博客总结一下，方便日后复习。
洛谷3373是一道线段树区间加乘模板（裸），今天就又敲了一遍，有几个地方是我自己觉得很重要的。
1.考虑是否要开Long Long。
2.乘的标记一开始赋为1，在标记下传后也要请为1（这个很简单，但我觉得容易忘）
3.在标记更新的时候一定要先乘后加，这个很重要。
4.乘标记更新时会对加标记造成影响，加标记更新时不会对乘标记造成影响。
void modify_c(int k,int L,int R,int l,int r,LL v) { if(L>=l&&R<=r) { mul[k]=mul[k]*v%p; add[k]=add[k]*v%p; sum[k]=sum[k]*v%p; return; } pushdown(k,L,R); int mid=(L+R)>>1; if(l<=mid) modify_c(lc[k],L,mid,l,r,v); if(r>mid) modify_c(rc[k],mid+1,R,l,r,v); sum[k]=(sum[lc[k]]+sum[rc[k]])%p; }
5.pushdown中更新下面的总值的时候不把要更新的点的add和mul也弄进去，因为它会在modify的时候被更新，在L>=l&&R<=r里。（具体看代码）
#include<bits/stdc++.h> #define LL long long #define N 100003 using namespace std; int p; int ndnum=1; LL sum[N<<2],mul[N<<2],add[N<<2],lc[N<<2],rc[N<<2],a[N]; int read() { int f=1,x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } void build(int k,int l,int r) { mul[k]=1; if(l==r) {sum[k]=a[l]%p;return;} int mid=(l+r)>>1; build(lc[k]=++ndnum,l,mid); build(rc[k]=++ndnum,mid+1,r); sum[k]=(sum[lc[k]]+sum[rc[k]])%p; } void pushdown(int k,int l,int r) { //为什么在pushdown中更新下面的总值的时候为什么不把要更新的点的mul也乘进去， //是因为在modify的时候我已经用他原来的mul值更新过一遍了，当然不需要乘进去 //add同理 //为什么要把mul的值和add的值又更新到要更新的点的mul和add上呢？ //这个则是因为后面又要pushdown的时候，一定要连着这个一起pushdown下去。 mul[lc[k]]=mul[lc[k]]*mul[k]%p; mul[rc[k]]=mul[rc[k]]*mul[k]%p; add[lc[k]]=add[lc[k]]*mul[k]%p; add[rc[k]]=add[rc[k]]*mul[k]%p; add[lc[k]]=(add[lc[k]]+add[k])%p; add[rc[k]]=(add[rc[k]]+add[k])%p; int mid=(l+r)>>1; sum[lc[k]]=sum[lc[k]]*mul[k]%p; sum[rc[k]]=sum[rc[k]]*mul[k]%p; sum[lc[k]]=(sum[lc[k]]+add[k]*(mid-l+1)%p)%p; sum[rc[k]]=(sum[rc[k]]+add[k]*(r-mid)%p)%p; add[k]=0;mul[k]=1; } void modify_add(int k,int L,int R,int l,int r,LL v) { if(L>=l&&R<=r) { add[k]=(add[k]+v)%p; sum[k]=(sum[k]+(R-L+1)*v)%p; return; } pushdown(k,L,R); int mid=(L+R)>>1; if(l<=mid)modify_add(lc[k],L,mid,l,r,v); if(r>mid)modify_add(rc[k],mid+1,R,l,r,v); sum[k]=(sum[lc[k]]+sum[rc[k]])%p; } void modify_c(int k,int L,int R,int l,int r,LL v) { if(L>=l&&R<=r) { mul[k]=mul[k]*v%p; add[k]=add[k]*v%p; sum[k]=sum[k]*v%p;//就是在这里，已经用他原来的mul值更新过一遍了,所以在pushdown的时候sum[lc[k]]是乘加mul[k]和add[k] return; } pushdown(k,L,R); int mid=(L+R)>>1; if(l<=mid) modify_c(lc[k],L,mid,l,r,v); if(r>mid) modify_c(rc[k],mid+1,R,l,r,v); sum[k]=(sum[lc[k]]+sum[rc[k]])%p; } LL query(int k,int L,int R,int l,int r) { if(L>=l&&R<=r) return sum[k]; int mid=(L+R)>>1; pushdown(k,L,R); LL ans=0; if(l<=mid) ans=(ans+query(lc[k],L,mid,l,r))%p; if(r>mid) ans=(ans+query(rc[k],mid+1,R,l,r))%p; return ans%p; } int main() { int n=read(),m=read();p=read(); for(int i=1;i<=n;++i) a[i]=read(); build(1,1,n); for(int i=1;i<=m;++i) { int op=read(),x=read(),y=read(); if(op==1) { LL k=read(); modify_c(1,1,n,x,y,k); } if(op==2) { LL k=read(); modify_add(1,1,n,x,y,k); } if(op==3) printf("%lld ",query(1,1,n,x,y)); } }
让我很无语的是调了好久样例过不了，最后发现是没有在main里写build。。。天，我是什么神仙。