原题链接：https://www.luogu.org/problem/show?pid=3373
其实也没啥好说的，就是注意一下乘法标记会影响到加法标记
#include<cstdio> void read(int &y) { y=0;char x=getchar();int f=1; while(x<‘0‘||x>‘9‘) {if(x==‘-‘) f=-1;x=getchar();} while(x>=‘0‘&&x<=‘9‘) {y=y*10+x-‘0‘;x=getchar();} y*=f; } long long data[400005],fm[400005],fa[400005]; int a[100005],p; void build(int o,int l,int r) { fm[o]=1; if(l==r) { data[o]=a[l]%p; return; } int mid=(l+r)>>1; build(o<<1,l,mid); build(o<<1|1,mid+1,r); data[o]=(data[o<<1]+data[o<<1|1])%p; } void putdown(int o,int l,int r) { int mid=(l+r)>>1; data[o<<1]=(data[o<<1]*fm[o]+fa[o]*(mid-l+1))%p; data[o<<1|1]=(data[o<<1|1]*fm[o]+fa[o]*(r-mid))%p; fm[o<<1]=fm[o<<1]*fm[o]%p; fm[o<<1|1]=fm[o<<1|1]*fm[o]%p; fa[o<<1]=(fa[o<<1]*fm[o]+fa[o])%p; fa[o<<1|1]=(fa[o<<1|1]*fm[o]+fa[o])%p; fm[o]=1; fa[o]=0; } void add(int ll,int rr,int k,int o,int l,int r) { if(ll<=l&&rr>=r) { data[o]=(data[o]+(r-l+1)*k)%p; fa[o]=(fa[o]+k)%p; return; } int mid=(l+r)>>1; putdown(o,l,r); if(mid>=ll) add(ll,rr,k,o<<1,l,mid); if(mid<rr) add(ll,rr,k,o<<1|1,mid+1,r); data[o]=(data[o<<1]+data[o<<1|1])%p; } void mul(int ll,int rr,int k,int o,int l,int r) { if(ll<=l&&rr>=r) { data[o]=(data[o]*k)%p; fm[o]=(fm[o]*k)%p; fa[o]=(fa[o]*k)%p; return; } int mid=(l+r)>>1; putdown(o,l,r); if(mid>=ll) mul(ll,rr,k,o<<1,l,mid); if(mid<rr) mul(ll,rr,k,o<<1|1,mid+1,r); data[o]=(data[o<<1]+data[o<<1|1])%p; } long long ask(int ll,int rr,int o,int l,int r) { if(ll<=l&&rr>=r) return data[o]; putdown(o,l,r); int mid=(l+r)>>1; long long ans=0; if(mid>=ll) ans+=ask(ll,rr,o<<1,l,mid); if(mid<rr) ans+=ask(ll,rr,o<<1|1,mid+1,r); return ans%p; } int main() { int n,m,op,l,r,k; read(n);read(m);read(p); for(int i=1;i<=n;i++) read(a[i]); build(1,1,n); while(m--) { read(op); if(op==1) { read(l);read(r);read(k); mul(l,r,k,1,1,n); } if(op==2) { read(l);read(r);read(k); add(l,r,k,1,1,n); } if(op==3) { read(l);read(r); printf("%lld\n",ask(l,r,1,1,n)); } } return 0; }
原文：http://www.cnblogs.com/zeroform/p/7633114.html