模板_线段树2

题目链接：【模板】线段树 2 （区间加法、乘法、查询）
题目标签：线段树
题目大意：给定一个序列，支持三种操作：区间加法、区间乘法和区间查询，输出每一次 _查询mod p_ 的结果。
题目分析：对于区间加法和区间查询，相信大家在AC完模板1后~~已经掌握了~~，那我们着重来分析一下 _区间乘法_ ，根据模板1的经验，我们可以想到——肯定还要打标记，但是怎样打一个合适的懒标记呢？
区间乘法的LazyTag
- 我们来假设一下，我们现在有集合S{a,b,c},当它们都加上一个数N，再乘上一个数M，会变成
  
  S{ (a+N) X M), ((b+N) X M),((c+N) X M) }
  (X意为乘号) 则又可以化为
  
  S{ (a X M+N X M), (b X M+N X M), (c X M+N X M) }
  即乘法分配律，由此我们可得 _子节点的加法标记要乘父节点的乘法标记加上父节点的加法标记_ ，化成代码即为
  1
  2
  3
  add[子节点]=(add[子节点]*mul[父节点]+add[父节点])%p;
  mul[子节点]=(mul[子节点]*mul[父节点])%p;
  data[子节点]=(data[子节点]*mul[父节点]+(r-l+1)*add[父节点])%p;
  所以这道题这样做就可以AC了！

下面是代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
#define Maxn 100010
using namespace std;
typedef long long ll;
ll sc() { //long long 快读 
	ll xx=0,ff=1; char cch;
	while(cch<'0'|| cch>'9') {
		if(cch=='-') ff=-ff; cch=gc;
	}
	while(cch>='0'&& cch<='9') {
		xx=xx*10+(cch-48); cch=gc;
	}
	return xx*ff;
}
ll n,m,p;
ll a[Maxn],data[Maxn*4],add[Maxn*4],mul[Maxn*4];
namespace DY {
	void ADD(ll k,ll l,ll r,ll v1,ll v2) { //添加标记，具体解释在上方 
		add[k]=(add[k]*v2+v1)%p;
		mul[k]=(mul[k]*v2)%p;
		data[k]=(data[k]*v2+(r-l+1)*v1)%p;
	}
	void pushdown(ll k,ll l,ll r,ll mid) { //下传标记 
		if(!add[k]&& mul[k]==1) return ;
		ADD(k<<1, l, mid, add[k], mul[k]);
		ADD(k<<1|1, mid+1, r, add[k], mul[k]);
		add[k]=0; mul[k]=1;
	}
	void modify(ll k,ll l,ll r,ll x,ll y,ll v1,ll v2) { //修改[x,y] 的数据 +v1 *v2 
		if(l>=x&& r<=y) return ADD(k,l,r,v1,v2); //添加标记 
		ll mid=l+r>>1;
		pushdown(k,l,r,mid); //下传标记 
		if(x<=mid) modify(k<<1, l, mid, x, y, v1, v2);
		if(y>mid) modify(k<<1|1, mid+1, r, x, y, v1, v2);
		data[k]=(data[k<<1]+data[k<<1|1])%p; //更新节点数据 
	}
	ll query(ll k,ll l,ll r,ll x,ll y) { //区间求和 
		if(l>=x&& r<=y) return data[k];
		ll mid=l+r>>1,res=0;
		pushdown(k,l,r,mid);
		if(x<=mid) res=query(k<<1, l, mid, x, y)%p;
		if(y>mid) res+=(query(k<<1|1, mid+1, r, x, y)%p);
		return res%p;
	}
	void build(ll k,ll l,ll r) { //建树 
		mul[k]=1; //乘法标记要赋初值为1 
		if(l==r) {
			data[k]=a[l];
			return ;
		}
		ll mid=l+r>>1;
		build(k<<1, l, mid);
		build(k<<1|1, mid+1, r);
		data[k]=(data[k<<1]+data[k<<1|1])%p; //更新节点数据 
	}
	void main() {
		n=sc(); m=sc(); p=sc();
		for(int i=1; i<=n; i++)
			a[i]=sc(); //输入原始序列 
		build(1,1,n); //建树 
		while(m--) {
			ll flag=sc();
			if(flag==1) { //区间乘法 
				ll u=sc(),v=sc(),num=sc();
				modify(1,1,n,u,v,0,num);
			}
			else if(flag==2) { //区间加法 
				ll u=sc(),v=sc(),num=sc();
				modify(1,1,n,u,v,num,1);
			}
			else { //区间求和 
				ll u=sc(),v=sc();
				printf("%lld\n",query(1,1,n,u,v));
			}
		}
	}
};
int main() {
	DY::main();
	return 0;
}

RP++

S{ (a+N) X M), ((b+N) X M),((c+N) X M) }

S{ (a X M+N X M), (b X M+N X M), (c X M+N X M) }

RP++