总算写出来了。。。线段树同时维护乘法和加法，欢迎体验！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include<iostream> using namespace std; struct segmentTree{ typedef long long ll; const static int MAX=100000; ll MOD; ll v[4*MAX],aTg[4*MAX],mTg[4*MAX]; inline static ll lson(ll r){return r*2;} inline static ll rson(ll r){return r*2+1;} void build(ll r,ll* a,ll s,ll e){ aTg[r]=0;mTg[r]=1; if(s==e){v[r]=a[s]%MOD;return;} ll m=(s+e)>>1; build(lson(r),a,s,m); build(rson(r),a,m+1,e); v[r]=(v[lson(r)]+v[rson(r)])%MOD; } void pushDown(ll r,ll s,ll e){ if(aTg[r]==0&&mTg[r]==1)return; ll m=(s+e)>>1; v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD; v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD; aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD; aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD; mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD; mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD; aTg[r]=0;mTg[r]=1; } ll query(ll r,ll cs,ll ce,ll qs,ll qe){ if(qe<cs||ce<qs)return 0; if(qs<=cs&&ce<=qe)return v[r]%MOD; pushDown(r,cs,ce); ll cmd=(cs+ce)>>1; return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD; } void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){ if(ue<cs||ce<us)return; if(us<=cs&&ce<=ue){ v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD; aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD; mTg[r]=(mTg[r]*mulv)%MOD; return; } pushDown(r,cs,ce); ll cmd=(cs+ce)>>1; update(lson(r),cs,cmd,us,ue,addv,mulv); update(rson(r),cmd+1,ce,us,ue,addv,mulv); v[r]=(v[lson(r)]+v[rson(r)])%MOD; } }ST; typedef long long ll; ll n,m,p; ll a[100005]; int main(){ ios::sync_with_stdio(false); cin>>n>>m>>p; for(int i=1;i<=n;i++)cin>>a[i]; ST.MOD=p; ST.build(1,a,1,n); for(int i=1;i<=m;i++){ ll op,x,y,k; cin>>op; if(op==1||op==2){ cin>>x>>y>>k; if(op==1)ST.update(1,1,n,x,y,0,k); else ST.update(1,1,n,x,y,k); }else{ cin>>x>>y; cout<<ST.query(1,1,n,x,y)%p<<endl; } } } |