线段树 30pts 求条

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e18,maxn=1e5+10;
int n,q,mod,a[maxn];
int w[4*maxn],tagadd[4*maxn],tagc[4*maxn];
void pushup(int id){
	w[id]=(w[id*2]+w[id*2+1])%mod;
}
void build(int id,int l,int r){
	if(l==r){
		w[id]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	pushup(id);
}
void maketag(int id,int op,int len,int k){
	if(op==1){
		tagc[id]*=k;
		tagadd[id]*=k;
		(w[id]*=k)%=mod;
	}
	else{
		tagadd[id]+=k;
		(w[id]+=len*k)%=mod;
	}
}
void pushdown(int id,int l,int r){
	int mid=(l+r)/2;
	maketag(id*2,1,mid-l+1,tagc[id]);
	maketag(id*2+1,1,r-mid,tagc[id]);
	maketag(id*2,2,mid-l+1,tagadd[id]);
	maketag(id*2+1,2,r-mid,tagadd[id]);
	tagc[id]=1;tagadd[id]=0;
}
bool inr(int l,int r,int cl,int cr){
	return cl<=l and r<=cr;
}
bool outr(int l,int r,int cl,int cr){
	return cr<l or r<cl;
}
void update(int id,int l,int r,int cl,int cr,int op,int k){
	if(inr(l,r,cl,cr)){
		maketag(id,op,r-l+1,k);
		return;
	}
	if(outr(l,r,cl,cr)){
		return;
	}
	pushdown(id,l,r);
	int mid=(l+r)/2;
	update(id*2,l,mid,cl,cr,op,k);
	update(id*2+1,mid+1,r,cl,cr,op,k);
	pushup(id);
}
int check(int id,int l,int r,int cl,int cr){
	if(inr(l,r,cl,cr)){
		return w[id];
	}
	if(outr(l,r,cl,cr)){
		return 0;
	}
	pushdown(id,l,r);
	int mid=(l+r)/2;
	return (check(id*2,l,mid,cl,cr)+check(id*2+1,mid+1,r,cl,cr))%mod;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>q>>mod;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]%=mod;
	}
	build(1,1,n);
	for(int i=1;i<=4*n;i++){
		tagc[i]=1;
	}
	while(q--){
		int op,x,y;cin>>op>>x>>y;
		if(op==3){
			cout<<check(1,1,n,x,y)<<"\n";
			continue;
		}
		int k;cin>>k;
		if(op==1){
			update(1,1,n,x,y,1,k);
		}
		else{
			update(1,1,n,x,y,2,k);
		}
	}
	return 0;
}