BZOJ 1798 [Ahoi2009]Seq 维护序列seq

starli posted @ 2016年2月01日 17:31 in 数据结构 , 194 阅读

线段树 

打两个标记,一个记录乘法一个记录加法,根据乘法分配律可以得到:标记下传的时候要先传乘法的标记再传加法的标记,下传乘法的时候要同时将子节点的加法标记也乘对应的数。

然后总结一下我自己犯的错误

1.标记下传时 判断无标记之后直接不操作 而不是把标记加上去 

2.线段树开始忘记build

3.开始的时候没有看到要取模

代码 

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=300010,NUL=-657558;
typedef long long LL;
LL sum[N*4],plus[N*4],mul[N*4],a[N],L[N*4],R[N*4],mod,m,op,x1,y1,z1,n;
void up(int x){sum[x]=(sum[x<<1]+sum[x<<1|1])%mod;}
void down(int x){
	if(mul[x]!=NUL) {
		(sum[x<<1]*=mul[x])%=mod;
		if(mul[x<<1]!=NUL) (mul[x<<1]*=mul[x])%=mod;else mul[x<<1]=mul[x]%mod;
		if(plus[x<<1]!=NUL) (plus[x<<1]*=mul[x])%=mod;
		(sum[x<<1|1]*=mul[x])%=mod;
		if(mul[x<<1|1]!=NUL) (mul[x<<1|1]*=mul[x])%=mod;else mul[x<<1|1]=mul[x]%mod;
		if(plus[x<<1|1]!=NUL) (plus[x<<1|1]*=mul[x])%=mod;
	}
	if(plus[x]!=NUL) {
		(sum[x<<1]+=plus[x]*(R[x<<1]-L[x<<1]+1)%mod)%=mod;
		if(plus[x<<1]!=NUL) (plus[x<<1]+=plus[x])%=mod;else plus[x<<1]=plus[x]%mod;
		(sum[x<<1|1]+=plus[x]*(R[x<<1|1]-L[x<<1|1]+1)%mod)%=mod;
		if(plus[x<<1|1]!=NUL) (plus[x<<1|1]+=plus[x])%=mod;else plus[x<<1|1]=plus[x]%mod;
	}
	mul[x]=plus[x]=NUL;
}
void build(int x,int l,int r){
	plus[x]=mul[x]=NUL;L[x]=l;R[x]=r;
	if(l==r) {sum[x]=a[l]; return;}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	up(x);
}
void change1(int x,int l,int r,int d){//plus
	int mid=(L[x]+R[x])>>1;
	if(l<=L[x] && R[x]<=r) {
		if(plus[x]!=NUL) (plus[x]+=d)%=mod;else plus[x]=d%mod;
		(sum[x]+=d*(R[x]-L[x]+1)%mod)%=mod;
		return;
	}
	down(x);
	if(mid<r) change1(x<<1|1,l,r,d);
	if(mid>=l) change1(x<<1,l,r,d);
	up(x);
}
void change2(int x,int l,int r,int d){//multiply
	int mid=(L[x]+R[x])>>1;
	if(l<=L[x] && R[x]<=r) {
		(sum[x]*=d%mod)%=mod;
		if(plus[x]!=NUL) (plus[x]*=d)%=mod;
		if(mul[x]!=NUL) (mul[x]*=d)%=mod; else mul[x]=d%mod;
		return;
	}
	down(x);
	if(mid<r) change2(x<<1|1,l,r,d);
	if(mid>=l) change2(x<<1,l,r,d);
	up(x);
}
LL ask(int x,int l,int r){
	int mid=(L[x]+R[x])>>1;
	LL ret=0;
	if(l<=L[x] && R[x]<=r) return sum[x];
	down(x);
	if(mid<r) (ret+=ask(x<<1|1,l,r))%=mod;
	if(mid>=l) (ret+=ask(x<<1,l,r))%=mod;
	return ret;
}
void print(){
	for(int i=1;i<=n;i++)
		printf("%lld ",ask(1,i,i));
	printf("\n");
}
int main(){
	//freopen("1798.in","r",stdin);freopen("1798.out","w",stdout);
	scanf("%lld%lld",&n,&mod);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	scanf("%lld",&m);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&op,&x1,&y1);
		if(op==1) {scanf("%lld",&z1);change2(1,x1,y1,z1);}
		if(op==2) {scanf("%lld",&z1);change1(1,x1,y1,z1);}
		if(op==3) {printf("%lld\n",ask(1,x1,y1));}
	//	print();
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter