mxqz 线段树板子

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;bool f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=0;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return f?x:-x;
}
int n,m,p,opt,l,r,x,a[100005],sum[400005],ad[400005],dd[400005]; 
void build(int x,int l,int r){
	dd[x]=1;
	if(l==r){
		sum[x]=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	sum[x]=(sum[x<<1]+sum[x<<1|1])%p;
}
void upd1(int x,int l1,int r1,int l2,int r2,int val){
	if(l2<=l1&&r1<=r2){
		ad[x]=1ll*ad[x]*val%p,dd[x]=1ll*dd[x]*val%p,sum[x]=1ll*sum[x]*val%p;
		return ;
	}
	int mid=l1+r1>>1;
	if(dd[x]>1){
		dd[x<<1]=1ll*dd[x<<1]*dd[x]%p,ad[x<<1]=1ll*ad[x<<1]*dd[x]%p,sum[x<<1]=1ll*sum[x<<1]*dd[x]%p,
		dd[x<<1|1]=1ll*dd[x<<1|1]*dd[x]%p,ad[x<<1|1]=1ll*ad[x<<1|1]*dd[x]%p,sum[x<<1|1]=1ll*sum[x<<1|1]*dd[x]%p,dd[x]=1;
	}
	if(ad[x]){
		(ad[x<<1]+=ad[x])%=p,sum[x<<1]=(1ll*sum[x<<1]+1ll*(mid-l1+1)*ad[x])%p,
		(ad[x<<1|1]+=ad[x])%=p,sum[x<<1|1]=(1ll*sum[x<<1|1]+1ll*(r1-mid)*ad[x])%p,ad[x]=0;
	}
	
	if(mid>=l2) upd1(x<<1,l1,mid,l2,r2,val);
	if(mid<r2) upd1(x<<1|1,mid+1,r1,l2,r2,val);
	sum[x]=(sum[x<<1]+sum[x<<1|1])%p; 
}
void upd2(int x,int l1,int r1,int l2,int r2,int val){
	if(l2<=l1&&r1<=r2){
		(ad[x]+=val)%=p,sum[x]=(1ll*sum[x]+1ll*val*(r1-l1+1))%p;
		return ;
	}
	int mid=l1+r1>>1;
	if(dd[x]>1){
		dd[x<<1]=1ll*dd[x<<1]*dd[x]%p,ad[x<<1]=1ll*ad[x<<1]*dd[x]%p,sum[x<<1]=1ll*sum[x<<1]*dd[x]%p,
		dd[x<<1|1]=1ll*dd[x<<1|1]*dd[x]%p,ad[x<<1|1]=1ll*ad[x<<1|1]*dd[x]%p,sum[x<<1|1]=1ll*sum[x<<1|1]*dd[x]%p,dd[x]=1;
	}
	if(ad[x]){
		(ad[x<<1]+=ad[x])%=p,sum[x<<1]=(1ll*sum[x<<1]+1ll*(mid-l1+1)*ad[x])%p,
		(ad[x<<1|1]+=ad[x])%=p,sum[x<<1|1]=(1ll*sum[x<<1|1]+1ll*(r1-mid)*ad[x])%p,ad[x]=0;
	}
	if(mid>=l2) upd2(x<<1,l1,mid,l2,r2,val);
	if(mid<r2) upd2(x<<1|1,mid+1,r1,l2,r2,val);
	sum[x]=(sum[x<<1]+sum[x<<1|1])%p; 
}
inline int query(int x,int l1,int r1,int l2,int r2){
	if(l2<=l1&&r1<=r2) return sum[x];
	int mid=l1+r1>>1;
	if(dd[x]>1){
		dd[x<<1]=1ll*dd[x<<1]*dd[x]%p,ad[x<<1]=1ll*ad[x<<1]*dd[x]%p,sum[x<<1]=1ll*sum[x<<1]*dd[x]%p,
		dd[x<<1|1]=1ll*dd[x<<1|1]*dd[x]%p,ad[x<<1|1]=1ll*ad[x<<1|1]*dd[x]%p,sum[x<<1|1]=1ll*sum[x<<1|1]*dd[x]%p,dd[x]=1;
	}
	if(ad[x]){
		(ad[x<<1]+=ad[x])%=p,sum[x<<1]=(1ll*sum[x<<1]+1ll*(mid-l1+1)*ad[x])%p,
		(ad[x<<1|1]+=ad[x])%=p,sum[x<<1|1]=(1ll*sum[x<<1|1]+1ll*(r1-mid)*ad[x])%p,ad[x]=0;
	}
	int ans=0;
	if(mid>=l2) ans+=query(x<<1,l1,mid,l2,r2);
	if(mid<r2) ans+=query(x<<1|1,mid+1,r1,l2,r2);
	return ans%p;
}
int main(){
	n=read(),m=read(),p=read();
	for(int i=1;i<=n;i++) a[i]=read()%p;
	build(1,1,n);
	while(m--){
		opt=read(),l=read(),r=read();
		if(opt==1){
			x=read()%p;
			upd1(1,1,n,l,r,x);
		}
		else if(opt==2){
			x=read()%p;
			upd2(1,1,n,l,r,x);
		}
		else printf("%d\n",query(1,1,n,l,r));
	}
    return 0;
}