说人话的线段树──懒人标记

• 引言：

线段树上的懒人标记一般只使用一个，加法或乘法，但如果加法和乘法一起出现呢？

例如：这道题（点我）。

• 代码核心：

此时标记下传函数需要做些更改。

但这里涉及一个加法和乘法的顺序问题，因为axb+c和(a+c)xb（即先加再乘与先乘再加）是不一样的

分开看一下：

假设当前节点c，要将标记下传至x。

记加法标记add，乘法标记mul，值val。

记更改后的标记为add'和mul'

1.先乘后加

有方程：

(x.val*x.mul+x.add)*c.mul+c.add=x.val*x.mul'+x.add'

不难解出：

x.mul'=x.mul*c.mul

x.add'=x.add*c.mul+c.add

好像还可以，继续

2.先加后乘

有方程：

[(x.val+x.add)*x.mul+c.add]*c.mul=(x.val+x.add')*x.mul'

不难解出：

x.add'=(x.add+c.add)/c.mul

x.mul'=x.mul*c.mul

注意！

出现了除法！

我们知道，除法不仅会影响答案的精度，有时还会出各种奇奇怪怪的问题

所以果断放弃后者，选择先乘后加。

• 学雷锋，放代码：

#include<bits/stdc++.h>
using namespace std;
long long mod,n,q,x,y,k;

struct Node{
	long long val,add,mul;
}tr[400007];

inline void out(long long x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) out(x/10);
     putchar(x%10+'0');
     return;
}

inline long long in(){
    long long X=0,w=0;
	char ch=0;
    while(!isdigit(ch)) 
		w|=ch=='-',ch=getchar();
    while(isdigit(ch)) 
		X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

inline void push(long long cur,long long l,long long r){
	long long son=cur<<1,mid=l+r>>1,len=mid-l+1,rep=2;
	while(rep--){
		tr[son].val=(tr[son].val*tr[cur].mul+len*tr[cur].add)%mod;
		tr[son].add=(tr[son].add*tr[cur].mul+tr[cur].add)%mod;
		tr[son].mul=(tr[son].mul*tr[cur].mul)%mod;
		son++,len=r-mid;
	}
	tr[cur].add=0,tr[cur].mul=1;
	return;
}

inline void build(long long cur,long long l,long long r){
	tr[cur].mul=1,tr[cur].add=0;
	if(l==r){
		tr[cur].val=in()%mod;
		return;
	}
	long long mid=l+r>>1,son=cur<<1;
	build(son,l,mid),build(son+1,mid+1,r);
	tr[cur].val=(tr[son].val+tr[son+1].val)%mod;
	return;
}

inline void mu(long long cur,long long l,long long r){
	if(x<=l&&r<=y){
		tr[cur].val=(tr[cur].val*k)%mod;
		if(l==r) return;
		tr[cur].mul=(tr[cur].mul*k)%mod;
		tr[cur].add=(tr[cur].add*k)%mod;
		return;
	}
	push(cur,l,r);
	long long mid=l+r>>1,son=cur<<1;
	if(x<=mid) mu(son,l,mid);
	if(y>mid) mu(son+1,mid+1,r);
	tr[cur].val=(tr[son].val+tr[son+1].val)%mod;
	return;
}

inline void ad(long long cur,long long l,long long r){
	if(x<=l&&r<=y){
		tr[cur].val=(tr[cur].val+k*(r-l+1))%mod;
		if(l==r) return;
		tr[cur].add=(tr[cur].add+k)%mod;
		return;
	}
	push(cur,l,r);
	long long mid=l+r>>1,son=cur<<1;
	if(x<=mid) ad(son,l,mid);
	if(y>mid) ad(son+1,mid+1,r);
	tr[cur].val=(tr[son].val+tr[son+1].val)%mod;
	return;
}

inline long long qu(long long cur,long long l,long long r){
	if(x<=l&&r<=y) return tr[cur].val;
	push(cur,l,r);
	long long re=0,mid=l+r>>1,son=cur<<1;
	if(x<=mid) re=(re+qu(son,l,mid))%mod;
	if(y>mid) re=(re+qu(son+1,mid+1,r))%mod;
	return re;
}

int main(){
	n=in(),q=in(),mod=in();
	build(1,1,n);
	while(q--){
		long long opt=in();
		x=in(),y=in();
		switch(opt){
			case 1:{
				k=in();
				mu(1,1,n);
				break;
			}
			case 2:{
				k=in();
				ad(1,1,n);
				break;
			}
			case 3:{
				out(qu(1,1,n));
				puts("");
				break;
			}
		}
	}
	return 0;
} 

• 总结：

这道题所囊括的思想是：

对于多重标记的操作，先规定操作，再推倒关系。