题目：https://www.luogu.org/problemnew/show/P3373
值和标记都是先乘后加。
别忘了加的时候乘上区间长度！！！
我的写法果然是要开4倍数组的。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=400005; typedef long long ll; ll a[N],f[N],lamul[N],laplu[N],n,m,p,L,R,k,zs; void pushup(ll cnt) { f[cnt]=f[cnt<<1]+f[cnt<<1|1]; } void pushdown(ll l,ll r,ll cnt) { ll ls=(cnt<<1),rs=(cnt<<1|1),mid=((l+r)>>1); f[ls]=(f[ls]*lamul[cnt]+laplu[cnt]*(mid-l+1))%p;////// lamul[ls]=(lamul[ls]*lamul[cnt])%p; laplu[ls]=(laplu[ls]*lamul[cnt]+laplu[cnt])%p; f[rs]=(f[rs]*lamul[cnt]+laplu[cnt]*(r-mid))%p;////// lamul[rs]=(lamul[rs]*lamul[cnt])%p; laplu[rs]=(laplu[rs]*lamul[cnt]+laplu[cnt])%p; lamul[cnt]=1;laplu[cnt]=0; } void build(ll l,ll r,ll cnt) { lamul[cnt]=1; if(l==r) { f[cnt]=a[l]; return; } ll mid=((l+r)>>1); build(l,mid,cnt<<1); build(mid+1,r,cnt<<1|1); pushup(cnt); } void mul(ll l,ll r,ll cnt) { if(l>=L&&r<=R) { f[cnt]=(f[cnt]*k)%p; lamul[cnt]=(lamul[cnt]*k)%p; laplu[cnt]=(laplu[cnt]*k)%p; return; } pushdown(l,r,cnt); ll mid=((l+r)>>1); if(mid>=L)mul(l,mid,cnt<<1); if(mid<R)mul(mid+1,r,cnt<<1|1); pushup(cnt); } void plu(ll l,ll r,ll cnt) { if(l>=L&&r<=R) { f[cnt]=(f[cnt]+k*(r-l+1))%p;///////乘长度 laplu[cnt]=(laplu[cnt]+k)%p; return; } pushdown(l,r,cnt); ll mid=((l+r)>>1); if(mid>=L)plu(l,mid,cnt<<1); if(mid<R)plu(mid+1,r,cnt<<1|1); pushup(cnt); } ll query(ll l,ll r,ll cnt) { if(l>=L&&r<=R) return f[cnt]; ll mid=((l+r)>>1),ans=0; pushdown(l,r,cnt); if(mid>=L)ans+=query(l,mid,cnt<<1); if(mid<R)ans+=query(mid+1,r,cnt<<1|1); return ans%p; } int main() { scanf("%lld%lld%lld",&n,&m,&p); for(ll i=1;i<=n;i++)scanf("%lld",&a[i]); build(1,n,1); for(ll i=1;i<=m;i++) { scanf("%lld%lld%lld",&zs,&L,&R); if(zs==1) { scanf("%lld",&k); mul(1,n,1); } if(zs==2) { scanf("%lld",&k); plu(1,n,1); } if(zs==3) printf("%lld ",query(1,n,1)%p); } return 0; }