做做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;
}