【Bzoj1798】维护序列seq

题意

线段树维护三个操作：区间加法，区间乘法，区间查询。

分析

需要打两个tag，注意先下放乘法之后再下放加法。 #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int maxx = 100000 + 50; LL T[maxx<<2],Add[maxx<<2],mul[maxx<<2]; LL mod,z; int n,m,pos,x,y; template <class T> void P(T &a,const T &b) {a=(a+b)%mod;return;} template <class T> void K(T &a,const T &b) {a=(a*b)%mod;return;} template <class T> void F(T &a,const T &b,const T &c) {a=(a*b+c)%mod;return;} namespace Y{ void Build(int i,int l,int r){ mul[i] = 1;Add[i] = 0;if(l == r) {scanf("%lld",&T[i]);return;} int mid = (l+r) >> 1;Build(i<<1,l,mid);Build(i<<1|1,mid+1,r); T[i] = (T[i<<1] + T[i<<1|1])%mod; } void pushdown(int i,int l,int r){ int mid = (l+r)>>1; K(mul[i<<1],mul[i]);K(mul[i<<1|1],mul[i]); F(Add[i<<1],mul[i],Add[i]);F(Add[i<<1|1],mul[i],Add[i]); F(T[i<<1],mul[i],(mid-l+1)*Add[i]); F(T[i<<1|1],mul[i],(r-mid)*Add[i]); mul[i] = 1;Add[i] = 0; } void modify(int i,int x,int y,int l,int r,LL k,int flag){ if(x<=l && r<=y) if(flag == 1) {K(mul[i],k);K(Add[i],k);K(T[i],k);return;} else if(flag == 2) {P(Add[i],k);P(T[i],(LL)(r-l+1)*k);return;} if((mul[i]!=1) || (Add[i]!=0)) pushdown(i,l,r);int V=(l+r)>>1; if(x <= V) modify(i<<1,x,y,l,V,k,flag); if(y > V) modify(i<<1|1,x,y,V+1,r,k,flag); T[i] = (T[i<<1] + T[i<<1|1])%mod; } LL Query(int i,int x,int y,int l,int r){ LL Ans = 0; if(x<=l && r<=y) return T[i];int V=(l+r)>>1; if((mul[i]!=1) || (Add[i]!=0)) pushdown(i,l,r); if(x <= V) P(Ans,Query(i<<1,x,y,l,V)); if(y > V) P(Ans,Query(i<<1|1,x,y,V+1,r)); return Ans; } } int main(){ scanf("%d%lld",&n,&mod);Y :: Build(1,1,n);scanf("%d",&m); while( m-- ){ scanf("%d%d%d",&pos,&x,&y); if(pos == 1||pos == 2) scanf("%lld",&z),Y :: modify(1,x,y,1,n,z,pos); if(pos == 3) printf("%lld\n",Y :: Query(1,x,y,1,n)); } return 0; } 模板的话还是短一点好嘛。