https://loj.ac/problem/10129板子题
板子
注意的就是，标记下放时 乘标记和加标记有优先顺序，先更新乘标记，再更新加标记，乘标记会影响加标记。
乘标记初始都为1；
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+5; int n; ll mod; ll sum[maxn*4],add[maxn*4],mul[maxn*4]; void pushdown(int l,int r,int p){ int len=r-l+1; int mid=(l+r)/2; if(add[p]||mul[p]!=1){ sum[p<<1]=sum[p<<1]*mul[p]%mod; sum[p<<1|1]=sum[p<<1|1]*mul[p]%mod; sum[p<<1]=(sum[p<<1]+add[p]*(mid-l+1))%mod; sum[p<<1|1]=(sum[p<<1|1]+add[p]*(r-mid))%mod; mul[p<<1]=mul[p<<1]*mul[p]%mod; mul[p<<1|1]=mul[p<<1|1]*mul[p]%mod; add[p<<1]=add[p<<1]*mul[p]%mod; add[p<<1|1]=add[p<<1|1]*mul[p]%mod; add[p<<1]=(add[p<<1]+add[p])%mod; add[p<<1|1]=(add[p<<1|1]+add[p])%mod; add[p]=0; mul[p]=1; } } void build(int l,int r,int p){ add[p]=0; mul[p]=1; if(l==r){ scanf("%lld",&sum[p]); sum[p]%=mod; return ; } int mid=(l+r)/2; build(l,mid,p<<1); build(mid+1,r,p<<1|1); sum[p]=(sum[p<<1]+sum[p<<1|1])%mod; } void update(int l,int r,int L,int R,int p,ll val,int f){ if(L<=l&&r<=R){ if(f){//乘 sum[p]=sum[p]*val%mod; mul[p]=mul[p]*val%mod; add[p]=add[p]*val%mod; }else{//加 sum[p]=(sum[p]+val*(r-l+1))%mod; add[p]=(add[p]+val)%mod; } return ; } pushdown(l,r,p); int mid=(l+r)/2; if(L<=mid) update(l,mid,L,R,p<<1,val,f); if(R>mid) update(mid+1,r,L,R,p<<1|1,val,f); sum[p]=(sum[p<<1]+sum[p<<1|1])%mod; } ll query(int l,int r,int L,int R,int p){ if(L<=l&&r<=R){ return sum[p]%mod; } pushdown(l,r,p); int mid=(l+r)/2; ll ans=0; if(L<=mid) ans=(ans+query(l,mid,L,R,p<<1))%mod; if(R>mid) ans=(ans+query(mid+1,r,L,R,p<<1|1))%mod; return ans%mod; } int main(){ scanf("%d%lld",&n,&mod); build(1,n,1); int m; scanf("%d",&m); while(m--){ int op,l,r; ll c; scanf("%d",&op); if(op==1){ scanf("%d%d%lld",&l,&r,&c); update(1,n,l,r,1,c,1); } else if(op==2){ scanf("%d%d%lld",&l,&r,&c); update(1,n,l,r,1,c,0); } else{ scanf("%d%d",&l,&r); printf("%lld\n",query(1,n,l,r,1)); } } return 0; }
