洛谷P3373 【模板】线段树 2

https://www.luogu.org/problemnew/show/P3373

题目描述
如题，已知一个数列，你需要进行下面三种操作：
将某区间每一个数乘上x
2.将某区间每一个数加上x
3.求出某区间每一个数的和

思路：addv表示加，mulv表示乘，一个区间同时有两种标记的话，规定先考虑乘，后考虑加，懒标记下传时，由于 $(v * m u l + a d d) * m u l 2 + a d d 2 = v * (m u l * m u l 2) + (a d d * m u l 2 + a d d 2)$ ，所以把两种标记按这样下传即可，更新和查询操作pushdown到目标区间即可。

#include<bits/stdc++.h>
using namespace std;
#define maxn (100000+100)
#define ll long long

ll n,m,mod,a[maxn];
ll op,ql,qr,val,_sum;

struct SegmentTree{
	ll sumv[maxn*4],addv[maxn*4],mulv[maxn*4];

	void build(int o,int l,int r)
	{
		if(l==r)sumv[o]=addv[o]=a[l],mulv[o]=1;
		else
		{
			int mid=(l+r)/2;
			build(o*2,l,mid);build(o*2+1,mid+1,r);
			sumv[o]=(sumv[o*2]+sumv[o*2+1])%mod;
			mulv[o]=1;
			addv[o]=0;
		}
	}

	void maintain(int o,int l,int r)
	{
		if(l==r)sumv[o]=addv[o]%mod;
		else
		{
			sumv[o]=(sumv[o*2]+sumv[o*2+1])%mod;
			sumv[o]=(sumv[o]*mulv[o])%mod;
			sumv[o]=(sumv[o]+(r-l+1)%mod*addv[o])%mod;
		}
	}

	void pushdown(int o)
	{
		mulv[o*2]*=mulv[o];mulv[o*2+1]*=mulv[o];
		addv[o*2]*=mulv[o];addv[o*2+1]*=mulv[o];
		mulv[o]=1;
		addv[o*2]+=addv[o];addv[o*2+1]+=addv[o];
		addv[o]=0;
		mulv[o*2]%=mod;mulv[o*2+1]%=mod;addv[o*2]%=mod;addv[o*2+1]%=mod;
	}

	void update(int o,int l,int r)
	{
		if(ql<=l&&qr>=r)
		{
			if(l==r)
			{
				if(op==1)addv[o]*=val;
				else addv[o]+=val;
				addv[o]%=mod;
			}
			else
			{
				if(op==1)mulv[o]*=val,addv[o]*=val,mulv[o]%=mod,addv[o]%=mod;
				else addv[o]+=val,addv[o]%=mod;
			}
			maintain(o,l,r);
		}	
		else
		{
			int mid=(l+r)/2;
			pushdown(o);
			if(ql<=mid)update(o*2,l,mid); else maintain(o*2,l,mid);
			if(qr>mid)update(o*2+1,mid+1,r); else maintain(o*2+1,mid+1,r);
		}
		maintain(o,l,r);		
	}

	void query(int o,int l,int r)
	{
		if(ql<=l && qr>=r)_sum=(_sum+sumv[o])%mod;
		else
		{
			int mid=(l+r)/2;
			pushdown(o);
			maintain(o*2,l,mid);maintain(o*2+1,mid+1,r);
			maintain(o,l,r);
			if(ql<=mid)query(o*2,l,mid);
			if(qr>mid)query(o*2+1,mid+1,r);
		}
	}
}tree;


int main()
{
	//freopen("input.in","r",stdin);
	cin>>n>>m>>mod;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]%=mod;
	tree.build(1,1,n);
	while(m--)
	{
		scanf("%lld%lld%lld",&op,&ql,&qr);
		if(op!=3)scanf("%lld",&val);
		if(op!=3)tree.update(1,1,n);
		else 
		{
			_sum=0;
			tree.query(1,1,n);
			printf("%lld\n",_sum);
		}
	}
	return 0;
}