https://www.luogu.org/problem/show?pid=3373
#include<iostream> #include<cstring> #include<cstdio> #define M 100000 #define LL long long using namespace std; struct H{ LL sum,l,r,len,addi,tim; }st[4*M+10];//四倍空间 LL MOD,n,m,a[M+10]; void build(LL o,LL l,LL r) { st[o].l=l,st[o].r=r,st[o].len=r-l+1; if(l==r){st[o].sum=a[l];return;} LL mid=(l+r)>>1; build(o<<1,l,mid); build(o<<1|1,mid+1,r); st[o].sum=(st[o<<1].sum+st[o<<1|1].sum)%MOD; } void pushdown(LL o) //难点 { st[o<<1].sum=((st[o<<1].sum*st[o].tim)%MOD+st[o].addi*st[o<<1].len)%MOD; st[o<<1|1].sum=((st[o<<1|1].sum*st[o].tim)%MOD+st[o].addi*st[o<<1|1].len)%MOD; st[o<<1].addi=((st[o<<1].addi*st[o].tim)%MOD+st[o].addi)%MOD; st[o<<1|1].addi=((st[o<<1|1].addi*st[o].tim)%MOD+st[o].addi)%MOD; st[o<<1].tim=(st[o].tim*st[o<<1].tim)%MOD; st[o<<1|1].tim=(st[o].tim*st[o<<1|1].tim)%MOD; st[o].tim=1,st[o].addi=0;//清空 } void tims(LL o,LL l,LL r,LL ql,LL qr,LL t) { int mid=(l+r)>>1; if(ql<=l&&qr>=r) { (st[o].tim*=(t%MOD))%=MOD; (st[o].addi*=(t%MOD))%=MOD; (st[o].sum*=(t%MOD))%=MOD; return; } if(st[o].tim!=1||st[o].addi) pushdown(o);//倍数有0！！！ if(ql<=mid) tims(o<<1,l,mid,ql,qr,t); if(qr>mid) tims(o<<1|1,mid+1,r,ql,qr,t); (st[o].sum=(st[o<<1].sum+st[o<<1|1].sum)%MOD)%=MOD; } void add(LL o,LL l,LL r,LL ql,LL qr,LL ax) { int mid=(l+r)>>1; if(ql<=l&&qr>=r){ (st[o].addi+=ax)%=MOD; (st[o].sum+=st[o].len*ax%MOD)%=MOD; return; } if(st[o].addi||st[o].tim!=1) pushdown(o); if(ql<=mid) add(o<<1,l,mid,ql,qr,ax); if(qr>mid) add(o<<1|1,mid+1,r,ql,qr,ax); (st[o].sum=(st[o<<1].sum+st[o<<1|1].sum)%MOD)%=MOD; } LL query(LL o,LL l,LL r,LL ql,LL qr) { int mid=(l+r)>>1; if(ql<=l&&qr>=r) return st[o].sum%MOD; if(st[o].tim!=1||st[o].addi) pushdown(o); LL anss=0; if(ql<=mid) (anss+=query(o<<1,l,mid,ql,qr))%=MOD; if(qr>mid) (anss+=query(o<<1|1,mid+1,r,ql,qr))%=MOD; return anss%MOD; } int main() { scanf("%lld%lld",&n,&MOD); for(LL i=1;i<=n;i++) scanf("%d",&a[i]); for(LL i=1;i<=4*M;i++) st[i].tim=1; build(1,1,n); scanf("%lld",&m); for(LL i=1;i<=m;i++) { LL p,l,r; LL c; scanf("%lld%lld%lld",&p,&l,&r); if(p==1) { scanf("%lld",&c);//乘c tims(1,1,n,l,r,c); } if(p==2) { scanf("%lld",&c);//加c add(1,1,n,l,r,c); } if(p==3) { LL ans=query(1,1,n,l,r); printf("%lld\n",ans); } } return 0; }需要注意的问题是，不要溢出；加和乘的关系；取模；倍数有0！
