30分求助

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=100010;
struct Tree{
	int l,r;
	long long val,sum,add;
}t[4*N];
int n,m,p,a[N];
void build(int x,int l,int r){ 
	t[x].l=l,t[x].r=r;t[x].val=1;
	if(l==r){
		t[x].sum=a[l]%p;
		return;
	}
	int mid=l+r>>1;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	t[x].sum=(t[x*2].sum+t[x*2+1].sum)%p;
}
void spread(int x){
	if(t[x].add){
		t[x*2].sum=(long long)(t[x].val*t[x*2].sum+(t[x].add*(t[x*2].r-t[x*2].l+1))%p)%p;
		t[x*2+1].sum=(long long)(t[x].val*t[x*2+1].sum+(t[x].add*(t[x*2+1].r-t[x*2+1].l+1))%p)%p;
		t[x*2].val=(long long)(t[x*2].val*t[x].val)%p;
		t[x*2+1].val=(long long)(t[x*2+1].val*t[x].val)%p;
		t[x*2].add=(long long)(t[x*2].add*t[x].val+t[x].add)%p;
		t[x*2+1].add=(long long)(t[x*2+1].add*t[x].val+t[x].add)%p;
		t[x].add=0;
		t[x].val=1;
	}
}
void change_1(int x,int l,int r,int k){
	if(l<=t[x].l&&r>=t[x].r){
		t[x].add=(t[x].add*k)%p;
		t[x].val=(t[x].val*k)%p;
		t[x].sum=(t[x].sum*k)%p;
		return;
	}
	spread(x);
	int mid=t[x].l+t[x].r>>1;
	if(l<=mid) change_1(x*2,l,r,k);
	if(r>mid) change_1(x*2+1,l,r,k);
	t[x].sum=(t[x*2].sum+t[x*2+1].sum)%p;
}
void change_2(int x,int l,int r,int k){
	if(l<=t[x].l&&r>=t[x].r){
		t[x].sum=(long long)(t[x].sum+k*(t[x].r-t[x].l+1))%p;
		t[x].add=(t[x].add+k)%p;
		return;
	}
	spread(x);
	int mid=t[x].l+t[x].r>>1;
	if(l<=mid) change_2(x*2,l,r,k);
	if(r>mid) change_2(x*2+1,l,r,k);
	t[x].sum=(t[x*2].sum+t[x*2+1].sum)%p;
}

long long ask(int x,int l,int r){
	if(l<=t[x].l&&r>=t[x].r) return t[x].sum;
	spread(x);
	int mid=t[x].l+t[x].r>>1;
	long long ans=0;
	if(l<=mid) ans=(ans+ask(x*2,l,r))%p;
	if(r>mid) ans=(ans+ask(x*2+1,l,r))%p;
	return ans;
}
int main(){
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	while(m--){
        int s,x,y,k;
		cin>>s>>x>>y;
		if(s==1){
			cin>>k;
			change_1(1,x,y,k);
		}
		if(s==2){
			cin>>k;
			change_2(1,x,y,k);
		}
		if(s==3) cout<<ask(1,x,y)%p<<endl;
	}
	return 0;
}