P3373 【模板】线段树 2

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,z,a[100005],k;
struct trees
{
	int l,r,num,lazy1,lazy2=1;
}t[400005];
void build(int l,int r,int g)
{
	t[g].lazy1=0,t[g].lazy2=1;
	t[g].l=l,t[g].r=r;
	if(l==r)
	{
		t[g].num=a[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,g*2);
	build(mid+1,r,g*2+1);
	t[g].num=t[g*2].num+t[g*2+1].num;
	return; 
}
void down(int g)
{
	if(t[g].lazy1!=0||t[g].lazy2!=1)
	{
		t[g*2].lazy1+=t[g].lazy1;
		t[g*2].num=(t[g*2].r-t[g*2].l+1)*t[g].lazy1;
		t[g*2+1].lazy1+=t[g].lazy1;
		t[g*2+1].num=(t[g*2+1].r-t[g*2].l+1)*t[g].lazy1;
		t[g].lazy1=0;
		
		t[g*2].lazy2*=t[g].lazy2;
		t[g*2].num=t[g*2].num*t[g].lazy2%k;
		t[g*2+1].lazy2*=t[g].lazy2;
		t[g*2+1].num=t[g*2+1].num*t[g].lazy2%k;
		t[g].lazy2=1;
	}
}
void mod(int l,int r,int num,int g)
{
	if(t[g].l>r||t[g].r<l)
	  return;
	if(t[g].l>=l&&t[g].r<=r)
	{
		t[g].lazy2*=num;
		t[g].num*=num;
		t[g].num%=k;
		return;
	}
	down(g);
	mod(l,r,num,g*2);
	mod(l,r,num,g*2+1);
	t[g].num=(t[g*2].num+t[g*2+1].num)%k;
	return;
}
void add(int l,int r,int num,int g)
{
	if(t[g].l>r||t[g].r<l)
	  return;
	if(t[g].l>=l&&t[g].r<=r)
	{
		t[g].lazy1+=num;
		t[g].num+=(t[g].r-t[g].l+1)*num;
		return;
	}
	down(g);
	add(l,r,num,g*2);
	add(l,r,num,g*2+1);
	t[g].num=t[g*2].num+t[g*2+1].num;
	return;
}
int ask(int l,int r,int g)
{
	if(t[g].l>r||t[g].r<l)
	  return 0;
	if(t[g].l>=l&&t[g].r<=r)
	{
		//cout<<t[g].l<<' '<<t[g].r<<' '<<t[g].num%k<<'\n';
		return t[g].num%k;
	}
	int ans=(ask(l,r,g*2)+ask(l,r,g*2+1))%k;
    //cout<<t[g].l<<' '<<t[g].r<<' '<<ans<<'\n';
	return ans;
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;++i)
	  cin>>a[i];
	build(1,n,1);
	while(m--)
	{
		cin>>x;
		if(x==1)
		{
			cin>>x>>y>>z;
			mod(x,y,z,1);
		}else
		    if(x==2)
		    {
		    	cin>>x>>y>>z;
		    	add(x,y,z,1);
			}else
			{
				cin>>x>>y;
				cout<<ask(x,y,1)%k<<'\n';
			}
	}
}//2 12 15 11 8