做做bzoj上的新题(不存在的) 同bzoj1798: [Ahoi2009]维护序列,样例都一样的...我能想象到的唯一的新的考察意义就是模数是2e9不是1e9,于是加法的时候需要转long long 就是给出一段序列,zici区间加一个数,区间乘一个数,区间求和...线段树开两个标记a,b表示乘上a再加b,nlogn完事.
#include<cstdio> const int maxn=100005; int n,mod; int seg[maxn<<2][3];//0:sum 1:multiply 2:plus void build(int rt,int l,int r){ if(l==r){ scanf("%d",&seg[rt][0]);seg[rt][1]=1;seg[rt][2]=0; }else{ int mid=(l+r)>>1; build(rt<<1,l,mid);build(rt<<1|1,mid+1,r); seg[rt][0]=(seg[rt<<1][0]+(long long)seg[rt<<1|1][0])%mod; seg[rt][1]=1;seg[rt][2]=0; } } void mult(int rt,int x){ seg[rt][0]=seg[rt][0]*1ll*x%mod; seg[rt][1]=seg[rt][1]*1ll*x%mod; seg[rt][2]=seg[rt][2]*1ll*x%mod; } void plus(int rt,int l,int r,int x){ seg[rt][0]=(seg[rt][0]+(r-l+1)*1ll*x)%mod; seg[rt][2]=(seg[rt][2]+x)%mod; } void pushdown(int rt,int l,int r){ if(seg[rt][1]!=1){ mult(rt<<1,seg[rt][1]);mult(rt<<1|1,seg[rt][1]); seg[rt][1]=1; } if(seg[rt][2]!=0){ int mid=(l+r)>>1; plus(rt<<1,l,mid,seg[rt][2]);plus(rt<<1|1,mid+1,r,seg[rt][2]); seg[rt][2]=0; } } void pushup(int rt){//assert(seg[rt][1]==1&&seg[rt][2]==0) seg[rt][0]=(seg[rt<<1][0]+seg[rt<<1|1][0])%mod; } int qsum(int rt,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr)return seg[rt][0]; pushdown(rt,l,r); int mid=(l+r)>>1; if(qr<=mid)return qsum(rt<<1,l,mid,ql,qr); if(ql>mid)return qsum(rt<<1|1,mid+1,r,ql,qr); return (qsum(rt<<1,l,mid,ql,qr)+qsum(rt<<1|1,mid+1,r,ql,qr))%mod; } void Mult(int rt,int l,int r,int ql,int qr,int x){ if(ql<=l&&r<=qr){ mult(rt,x);return; } pushdown(rt,l,r); int mid=(l+r)>>1; if(ql<=mid)Mult(rt<<1,l,mid,ql,qr,x); if(qr>mid)Mult(rt<<1|1,mid+1,r,ql,qr,x); pushup(rt); } void Plus(int rt,int l,int r,int ql,int qr,int x){ if(ql<=l&&r<=qr){ plus(rt,l,r,x);return; } pushdown(rt,l,r); int mid=(l+r)>>1; if(ql<=mid)Plus(rt<<1,l,mid,ql,qr,x); if(qr>mid)Plus(rt<<1|1,mid+1,r,ql,qr,x); pushup(rt); } int main(){ scanf("%d%d",&n,&mod); build(1,1,n); int tests;scanf("%d",&tests); int op,l,r,x; while(tests--){ scanf("%d%d%d",&op,&l,&r); if(op==3)printf("%d\n",qsum(1,1,n,l,r)); else{ scanf("%d",&x); if(op==1)Mult(1,1,n,l,r,x); else Plus(1,1,n,l,r,x); } } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7532140.html
