贴代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MAXN=1e5+5;
int n,q,m,tmp[MAXN],f[MAXN<<2],v1[MAXN<<2],v2[MAXN<<2];
inline void buildtree(int k,int l,int r){
	v2[k]=1;
	if(l==r){
		f[k]=tmp[l]%m;
		return ;
	}
	int mid=(l+r)>>1;
	buildtree(k+k,l,mid);
	buildtree(k+k+1,mid+1,r);
	f[k]=(f[k+k]+f[k+k+1])%m;
}
inline void add(int k,int l,int r,int x,int y,int z){
	if(l==x&&r==y){
		v1[k]=(v1[k]+z)%m;
		return ;
	}
	v2[k+k]=(v2[k+k]*v2[k])%m,v2[k+k+1]=(v2[k+k+1]*v2[k])%m,v2[k]=1;
	v1[k+k]=(v1[k+k]+v1[k])%m,v1[k+k+1]=(v1[k+k+1]+v1[k])%m,v1[k]=0;
	int mid=(l+r)>>1;
	if(y<=mid){
		add(k+k,l,mid,x,y,z);
	}
	else{
		if(x>mid){
			add(k+k+1,mid+1,r,x,y,z);
		}
		else{
			add(k+k,l,mid,x,mid,z),add(k+k+1,mid+1,r,mid+1,y,z);
		}
	}
	f[k]=(f[k+k]*v2[k]+v1[k+k]*(mid-l+1)+f[k+k+1]*v2[k+k+1]+v1[k+k+1]*(r-mid))%m;
}
inline void mul(int k,int l,int r,int x,int y,int z){
	if(l==x&&r==y){
		v2[k]=(v2[k]*z)%m;
		v1[k]=(v1[k]*z)%m;
		return ;
	}
	v2[k+k]=(v2[k+k]*v2[k])%m,v2[k+k+1]=(v2[k+k+1]*v2[k])%m,v2[k]=1;
	v1[k+k]=(v1[k+k]+v1[k])%m,v1[k+k+1]=(v1[k+k+1]+v1[k])%m,v1[k]=0;
	int mid=(l+r)>>1;
	if(y<=mid){
		mul(k+k,l,mid,x,y,z);
	}
	else{
		if(x>mid){
			mul(k+k+1,mid+1,r,x,y,z);
		}
		else{
			mul(k+k,l,mid,x,mid,z),mul(k+k+1,mid+1,r,mid+1,y,z);
		}
	}
	f[k]=(f[k+k]*v2[k]+v1[k+k]*(mid-l+1)+f[k+k+1]*v2[k+k+1]+v1[k+k+1]*(r-mid))%m;
}
int calc(int k,int l,int r,int s,int t){
	
	if(l==s&&r==t){
		return (f[k]*v2[k]+v1[k]*(r-l+1))%m;
	}
	v2[k+k]=(v2[k+k]*v2[k])%m,v2[k+k+1]=(v2[k+k+1]*v2[k])%m,v2[k]=1;
	v1[k+k]=(v1[k+k]+v1[k])%m,v1[k+k+1]=(v1[k+k+1]+v1[k])%m,v1[k]=0;
	int mid=(l+r)>>1,res=0;
	if(t<=mid){
		res=calc(k+k,l,mid,s,t)%m;
	}
	else{
		if(s>mid){
			res=calc(k+k+1,mid+1,r,s,t)%m;
		}
		else{
			res=(calc(k+k,l,mid,s,mid)%m+calc(k+k+1,mid+1,r,mid+1,t)%m)%m;
		}
	}
	f[k]=(f[k+k]*v2[k]+v1[k+k]*(mid-l+1)+f[k+k+1]*v2[k+k+1]+v1[k+k+1]*(r-mid))%m;
	return res;
}
signed main(){
	std::ios::sync_with_stdio(false);
	cin>>n>>q>>m;
	for(int i=1;i<=n;i++){
		cin>>tmp[i];
	}
	buildtree(1,1,n);
	for(int i=1;i<=q;i++){
		int op,x,y,k;
		cin>>op>>x>>y;
		if(op==1){
			cin>>k;
			mul(1,1,n,x,y,k);
		}
		else if(op==2){
			cin>>k;
			add(1,1,n,x,y,k);
		}
		else{
			cout<<calc(1,1,n,x,y)%m<<endl;
		}
	}
	return 0;
}