原题链接
线段树 加乘混合修改 主要是lazy的pushdown 代码意义明确就不解释了
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<queue> #include<vector> #include<climits> #include<string> #include<cstdlib> #include<ctime> #define MOD 1000000007 #define LL long long using namespace std; struct nico { LL lef,rig,len,lazy1,lazy2,sum; }point[400005]; LL n,P; LL a[100005]; void build(LL l,LL r,LL p) { LL mid; point[p].lef=l; point[p].rig=r; point[p].len=r-l+1; point[p].lazy2=1; if(l==r) { point[p].sum=a[l]%P; return; } mid=(l+r)>>1; build(l,mid,p<<1); build(mid+1,r,p<<1|1); point[p].sum=(point[p<<1].sum+point[p<<1|1].sum)%P; } void pushdown(LL p) { point[p<<1].sum=((point[p<<1].sum*point[p].lazy2)%P+(point[p].lazy1*point[p<<1].len)%P)%P; point[p<<1|1].sum=((point[p<<1|1].sum*point[p].lazy2)%P+(point[p].lazy1*point[p<<1|1].len)%P)%P; point[p<<1].lazy1=(point[p<<1].lazy1*point[p].lazy2+point[p].lazy1)%P; point[p<<1|1].lazy1=(point[p<<1|1].lazy1*point[p].lazy2+point[p].lazy1)%P; point[p<<1].lazy2=(point[p<<1].lazy2*point[p].lazy2)%P; point[p<<1|1].lazy2=(point[p<<1|1].lazy2*point[p].lazy2)%P; point[p].lazy1=0; point[p].lazy2=1; } void add(LL l,LL r,LL x,LL p) { LL mid; if(l==point[p].lef&&r==point[p].rig) { point[p].lazy1=(point[p].lazy1+x)%P; point[p].sum=(point[p].sum+((x%P)*(point[p].len%P))%P)%P; return; } pushdown(p); mid=(point[p].lef+point[p].rig)>>1; if(l>mid) add(l,r,x,p<<1|1); else if(r<=mid) add(l,r,x,p<<1); else if(l>=point[p].lef&&r<=point[p].rig) {add(l,mid,x,p<<1);add(mid+1,r,x,p<<1|1);} point[p].sum=(point[p<<1].sum+point[p<<1|1].sum)%P; } void change(LL l,LL r,LL x,LL p) { LL mid; if(l==point[p].lef&&r==point[p].rig) { point[p].lazy1=(point[p].lazy1*x)%P; point[p].lazy2=(point[p].lazy2*x)%P; point[p].sum=((point[p].sum%P)*(x%P))%P; return; } pushdown(p); mid=(point[p].lef+point[p].rig)>>1; if(l>mid) change(l,r,x,p<<1|1); else if(r<=mid) change(l,r,x,p<<1); else if(l>=point[p].lef&&r<=point[p].rig) {change(l,mid,x,p<<1);change(mid+1,r,x,p<<1|1);} point[p].sum=(point[p<<1].sum+point[p<<1|1].sum)%P; } LL ask(LL l,LL r,LL p) { LL mid; if(l==point[p].lef&&r==point[p].rig) return point[p].sum%P; pushdown(p); mid=(point[p].lef+point[p].rig)>>1; if(l>mid) return ask(l,r,p<<1|1); else if(r<=mid) return ask(l,r,p<<1); else if(l>=point[p].lef&&r<=point[p].rig) return (ask(l,mid,p<<1)%P)+(ask(mid+1,r,p<<1|1)%P); } LL m,i,f,t,g,c,ans; int main() { scanf("%lld%lld",&n,&P); for(i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,n,1); scanf("%lld",&m); for(i=1;i<=m;i++) { scanf("%lld",&f); if(f==1) { scanf("%lld%lld%lld",&t,&g,&c); change(t,g,c,1); } if(f==2) { scanf("%lld%lld%lld",&t,&g,&c); add(t,g,c,1); } if(f==3) { scanf("%lld%lld",&t,&g); ans=ask(t,g,1)%P; printf("%lld\n",ans); } } return 0; }