萌新刚学线段树，求调P3373:

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
struct node
{
	int l,r;
	int sum,add,mul;
}tr[N*4];
int a[N],n,p,m;
void pushup(int u){
	tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}
void emul(node &t,int add,int mul)
{
	t.sum=(t.sum*mul+add*(t.r-t.l+1))%p;
	t.add=(t.add*mul+add)%p;
	t.mul=(t.mul*mul)%p;
}
void pushdown(int u)
{
	emul(tr[u<<1],tr[u].add,tr[u].mul);
	emul(tr[u<<1|1],tr[u].add,tr[u].mul);
	tr[u].add=0;tr[u].mul=1;
}
void build(int u,int l,int r)
{
	tr[u]={l,r,0,0,1};
	if(l==r)
	{
		tr[u].sum=a[l]%p;
		return ;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);build(u<<1|1,mid+1,r);
	pushup(u);
}
void modify(int u,int l,int r,int mul,int add)
{
	if(l<=tr[u].l&&tr[u].r<=r) {
		emul(tr[u],add,mul);
		return ;
	}
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) modify(u<<1,l,r,mul,add);
	if(r>mid) modify(u<<1|1,l,r,mul,add);
	pushup(u); 
}

int query(int u,int l,int r)
{
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum%p;
	
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	int sum=0;
	if(l<=mid) sum=(long long)query(u<<1,l,r)%p;
	if(r>mid) sum=(sum+query(u<<1|1,l,r))%p ;
	return sum;
}
int main()
{
	scanf("%d%d%d",&n,&m,&p);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int op,l,r,c;
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d%d",&l,&r,&c);
			modify(1,l,r,c,0);
		}
		else if(op==2)
		{
			scanf("%d%d%d",&l,&r,&c);
			modify(1,l,r,1,c);
		}
		else{
			scanf("%d%d",&l,&r);
			cout<<query(1,l,r)%p<<endl;
		}
	}
	return 0;
}