BZOJ 1798 [Ahoi2009]Seq 维护序列seq 线段树

题意:链接方法:线段树解析:俩标记sb题更新乘的时候更新加完了代码:using namespace std;typedef long long ll;ll mul[N<<2],sum[N<<2],add[N<<2];ll n,mod;int q;void pushup(int rt){sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;}void pushdown(int rt,ll m){if(mul[rt]!=1||add[rt]!=0){mul[rt<<1]=(mul[rt<<1]*mul[rt])%mod;mul[rt<<1|1]=(mul[rt<<1|1]*mul[rt])%mod;add[rt<<1]=(mul[rt]*add[rt<<1]+add[rt])%mod;add[rt<<1|1]=(mul[rt]*add[rt<<1|1]+add[rt])%mod;sum[rt<<1]=(sum[rt<<1]*mul[rt]+(m-(m>>1))*add[rt])%mod;sum[rt<<1|1]=(sum[rt<<1|1]*mul[rt]+(m>>1)*add[rt])%mod;mul[rt]=1,add[rt]=0;}}void build(int l,int r,int rt){mul[rt]=1,sum[rt]=0;if(l==r){scanf(“%I64d”,&sum[rt]);return;}int mid=(l+r)>>1;build(lson),build(rson);pushup(rt);}void update_mul(int L,int R,int l,int r,int rt,ll c){if(L<=l&&r<=R){mul[rt]=(mul[rt]*c)%mod;add[rt]=(add[rt]*c)%mod;sum[rt]=(sum[rt]*c)%mod;return;}pushdown(rt,r-l+1);int mid=(l+r)>>1;if(L<=mid)update_mul(L,R,lson,c);if(R>mid) update_mul(L,R,rson,c);pushup(rt);}void update_add(int L,int R,int l,int r,int rt,ll c){if(L<=l&&r<=R){add[rt]=(add[rt]+c)%mod;sum[rt]=(sum[rt]+(r-l+1)*c)%mod;return;}pushdown(rt,r-l+1);int mid=(l+r)>>1;if(L<=mid)update_add(L,R,lson,c);if(R>mid)update_add(L,R,rson,c);pushup(rt);}ll query(int L,int R,int l,int r,int rt){ll ret=0;if(L<=l&&r<=R){return sum[rt];}pushdown(rt,r-l+1);int mid=(l+r)>>1;if(L<=mid)ret=(ret+query(L,R,lson))%mod;if(R>mid)ret=(ret+query(L,R,rson))%mod;pushup(rt);return ret;}int main(){scanf(“%lld%lld”,&n,&mod);build(1,n,1);scanf(“%d”,&q);while(q–){int opt;scanf(“%d”,&opt);int x,y;scanf(“%d%d”,&x,&y);ll z;switch(opt){case 1:scanf(“%lld”,&z);update_mul(x,y,1,n,1,z);break;case 2:scanf(“%lld”,&z);update_add(x,y,1,n,1,z);break;case 3:printf(“%lld\n”,query(x,y,1,n,1));break;}}}

，看不见我将要去的地方，记不得我已经去过的地方。