题目：https://www.luogu.org/problemnew/show/P3373
带乘的线段树，更新时把加的标记也乘一下，然后取值时先乘后加。
代码如下：
#include<iostream> #include<cstdio> #define ll long long using namespace std; int const N=100005; int n,m,p; ll t[N<<2],lc[N<<2],lj[N<<2],a[N<<2]; void pushup(int x) { t[x]=(t[x<<1]+t[x<<1|1])%p; } void pushdown(int l,int r,int x) { int ls=(x<<1),rs=(x<<1|1); int mid=(l+r)/2; t[ls]*=lc[x];t[ls]+=lj[x]*(mid-l+1);//! t[rs]*=lc[x];t[rs]+=lj[x]*(r-mid);//! lj[ls]*=lc[x];lj[ls]+=lj[x]; lj[rs]*=lc[x];lj[rs]+=lj[x]; lc[ls]*=lc[x];lc[rs]*=lc[x]; lj[x]=0;lc[x]=1; t[ls]%=p;t[rs]%=p; lj[ls]%=p;lj[rs]%=p; lc[ls]%=p;lc[rs]%=p; } void build(int l,int r,int x) { lc[x]=1;lj[x]=0; if(l==r) { t[x]=a[l]; return; } int mid=(l+r)/2; build(l,mid,x<<1); build(mid+1,r,x<<1|1); pushup(x); } void update(int l,int r,int L,int R,int s,int tp,int x) { if(tp==1)//c { if(l>=L&&r<=R) { lj[x]=(lj[x]*s)%p; lc[x]=(lc[x]*s)%p; t[x]=(t[x]*s)%p; return; } pushdown(l,r,x); int mid=(l+r)/2; if(mid>=L)update(l,mid,L,R,s,tp,x<<1); if(mid<R)update(mid+1,r,L,R,s,tp,x<<1|1); pushup(x); } if(tp==2)//j { if(l>=L&&r<=R) { lj[x]=(lj[x]+s)%p; t[x]=(t[x]+s*(r-l+1))%p;//! return; } pushdown(l,r,x); int mid=(l+r)/2; if(mid>=L)update(l,mid,L,R,s,tp,x<<1); if(mid<R)update(mid+1,r,L,R,s,tp,x<<1|1); pushup(x); } } ll query(int l,int r,int L,int R,int x) { if(l>=L&&r<=R)return t[x]; pushdown(l,r,x); int mid=(l+r)/2,ans=0; if(mid>=L)ans=(ans+query(l,mid,L,R,x<<1))%p; if(mid<R)ans=(ans+query(mid+1,r,L,R,x<<1|1))%p; return ans; } int main() { scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,n,1); while(m--) { int x,y,k,j; scanf("%d",&j); if(j==1) { scanf("%d%d%d",&x,&y,&k); update(1,n,x,y,k,1,1); } if(j==2) { scanf("%d%d%d",&x,&y,&k); update(1,n,x,y,k,2,1); } if(j==3) { scanf("%d%d",&x,&y); printf("%lld ",query(1,n,x,y,1)%p); } } return 0; }