7-25 线段树

常规
1

7-25 线段树

组员；林育辰，郑荣，许文博，刘天顺

建树build:

#define ls cur<<1;
#define rs cur<<1|1;
void push_up(int cur){
	node[cur]=(node[ls]+node[rs])%p;
}
void build(int cur,int l,int r){
	mult[cur]=1, add[cur]=0;  //mult[]乘法懒标记 add[]加法懒标记;
	if(l==r){
		node[cur]=a[l]%p;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(cur);       //累加
}

区间加、乘:

void up_data_add(int cur,int l,int r,int x,int y,int k){
	if(x<=l&&y>=r){
		mul(cur,l,r,k,1);
		return;
	}
	push_down(cur,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) up_data_add(ls,l,mid,x,y,k);
	if(y>mid) up_data_add(rs,mid+1,r,x,y,k);
	push_up(cur);
}

void up_data_mul(int cur,int l,int r,int x,int y,int k){
	if(x<=l&&y>=r){
		mul(cur,l,r,0,k);
		return;
	}
	push_down(cur,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) up_data_mul(ls,l,mid,x,y,k);
	if(y>mid) up_data_mul(rs,mid+1,r,x,y,k);
	push_up(cur);
}

下传懒标记:

void mul(int cur,int l,int r,int k,int m){
	node[cur]=((node[cur]*m)%p+(r-l+1)*k)%p;
	mult[cur]=m*mult[cur]%p;
	add[cur]=(add[cur]*m+k)%p;
}

void push_down(int cur,int l,int r){
	int mid=(l+r)>>1;
	mul(ls,l,mid,add[cur],mult[cur]);
	mul(rs,mid+1,r,add[cur],mult[cur]);
	add[cur]=0;
	mult[cur]=1;
}