rt 题目

#include<bits/stdc++.h>
#define N 100005
using namespace std;
long long sum[N*4],sumadd[N*4],n,m,a[N*4],b,x2,y2,k2,mod,lazy[N*4];
void pushup(int k){
	sum[k]=sum[k<<1]%mod+sum[k<<1|1]%mod;
}
void build(long long k,long long l,long long r)
{
	lazy[k]=1;
	if(l==r)
	{
		sum[k]=a[l];
		return;
	}
	long long mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	pushup(k);
}
void add(long long k,long long l,long long r,long long x)
{
	sumadd[k]+=x;
	sum[k]=sum[k]+(r-l+1)*x%mod;
	return;
}
void Add(long long k,long long l,long long r,long long x)
{
	lazy[k]*=x;
	sumadd[k]*=x;
	sum[k]=sum[k]*x%mod;
	return;
}
void Pushdown(long long k,long long l,long long r,long long mid)
{
	if(lazy[k]==1)
	{
		return;
	}
	Add(k*2,l,mid,lazy[k]);
	Add(k*2+1,mid+1,r,lazy[k]);
	pushup(k);
	lazy[k]=1;
}
void pushdown(long long k,long long l,long long r,long long mid)
{
	if(sumadd[k]==0)
	{
		return;
	}
	add(k*2,l,mid,sumadd[k]);
	add(k*2+1,mid+1,r,sumadd[k]);
	pushup(k);
	sumadd[k]=0;
}
void modify(long long k,long long l,long long r,long long x,long long y,long long v)
{
//	cout<<l<<" "<<r<<endl;
	if(r<x||l>y)return;
	if(l>=x&&r<=y)
	{
		add(k,l,r,v);
		return;
	}
	int mid=(l+r)/2;
	pushdown(k,l,r,mid);
	modify(k*2,l,mid,x,y,v);
	modify(k*2+1,mid+1,r,x,y,v);
	pushup(k);
}
void Modify(long long k,long long l,long long r,long long x,long long y,long long v)
{
//	cout<<l<<" "<<r<<endl;
	if(r<x||l>y)return;
	if(l>=x&&r<=y)
	{
		Add(k,l,r,v);
		return;
	}
	int mid=(l+r)/2;
	pushdown(k,l,r,mid);
	Modify(k*2,l,mid,x,y,v);
	Modify(k*2+1,mid+1,r,x,y,v);
	pushup(k);
}
long long query(long long k,long long l,long long r,long long x,long long y)
{
	if(l>=x&&r<=y)
	{
		return sum[k];
	}
	long long mid=(l+r)/2,res=0;
	pushdown(k,l,r,mid);
	if(x<=mid)
	{
		res+=query(k*2,l,mid,x,y);
	}
	if(mid<y)
	{
		res+=query(k*2+1,mid+1,r,x,y);
	}
	return res;
}
int main()
{
	cin>>n>>m>>mod;
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	for(long long i=1;i<=m;i++)
	{
		cin>>b;
		if(b==1)
		{
			cin>>x2>>y2>>k2;
			Modify(1,1,n,x2,y2,k2);
		}
		else if(b==2)
		{
			cin>>x2>>y2>>k2;
			modify(1,1,n,x2,y2,k2);
		}
		else{
			cin>>x2>>y2;
			cout<<query(1,1,n,x2,y2)%mod<<endl;
		}
	}
	return 0;
}