P3373 线段树 70pts 求调

#include<bits/stdc++.h>
#define int long long
#define maxn 100005
#define lc p<<1
#define rc (p<<1)+1
using namespace std;
int n,q,mod,a[maxn];
struct node{
	int left,right,add,mul,data;
}tree[maxn<<2];
void build(int p,int l,int r){
	tree[p].left=l,tree[p].right=r;
	if(l==r) tree[p].data=a[l]%mod;
	else{
		int mid=(l+r)>>1;
		build(lc,l,mid);build(rc,mid+1,r);
		tree[p].data=(tree[lc].data+tree[rc].data)%mod;
	}
}
void lazy(int p){
	if(tree[p].add||tree[p].mul>1){
		tree[lc].data=(tree[p].mul*tree[lc].data%mod+(tree[lc].right-tree[lc].left+1)*tree[p].add%mod)%mod;
		tree[rc].data=(tree[p].mul*tree[rc].data%mod+(tree[rc].right-tree[rc].left+1)*tree[p].add%mod)%mod;
		tree[lc].mul=tree[lc].mul*tree[p].mul%mod;
		tree[rc].mul=tree[rc].mul*tree[p].mul%mod;
		tree[lc].add=(tree[p].add%mod+tree[p].mul*tree[lc].add)%mod;
		tree[rc].add=(tree[p].add%mod+tree[p].mul*tree[rc].add)%mod;
		tree[p].mul=1,tree[p].add=0;
	}
}
void add(int p,int l,int r,int k){
	if(l<=tree[p].left&&r>=tree[p].right){
		tree[p].data=(tree[p].data%mod+(tree[p].right-tree[p].left+1)*k%mod)%mod;
		tree[p].add=(tree[p].add+k)%mod;
	}
	else{
		lazy(p);
		int mid=(tree[p].left+tree[p].right)>>1;
		if(l<=mid) add(lc,l,r,k);
		if(r>mid) add(rc,l,r,k);
		tree[p].data=(tree[lc].data+tree[rc].data)%mod;
	}
}
void mul(int p,int l,int r,int k){
	if(l<=tree[p].left&&r>=tree[p].right){
		tree[p].data=(tree[p].data*k)%mod;
		tree[p].add=tree[p].add*k%mod;
		tree[p].mul=tree[p].mul*k%mod;
	}
	else{
		lazy(p);
		int mid=(tree[p].left+tree[p].right)>>1;
		if(l<=mid) mul(lc,l,r,k);
		if(r>mid) mul(rc,l,r,k);
		tree[p].data=(tree[lc].data+tree[rc].data)%mod;
	}
}
int Ask(int p,int l,int r){
	if(tree[p].left>=l&&tree[p].right<=r) return tree[p].data;
	else{
		lazy(p);
		int ans=0;
		int mid=(tree[p].left+tree[p].right)>>1;
		if(l<=mid) ans=(ans+Ask(lc,l,r))%mod;
		if(r>mid) ans=(ans+Ask(rc,l,r))%mod;
		return ans;
	}
}
signed main()
{
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	scanf("%lld%lld%lld",&n,&q,&mod);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=(maxn<<2);i++){
		tree[i].mul=1;
	}
	while(q--){
		int opt,x,y,k;
		cin>>opt;
		if(opt==1){
			scanf("%lld%lld%lld",&x,&y,&k);
			mul(1,x,y,k);
		}
		else if(opt==2){
			scanf("%lld%lld%lld",&x,&y,&k);
			add(1,x,y,k);
		}
		else{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",Ask(1,x,y));
		}
	} 
}