#include<bits/stdc++.h>
using namespace std;
int n;
long long p;
int m;
long long arr[100001];
long long tree[400004];
queue<pair<int,long long> > lazy[400004];
inline void pushdown(const int &k,const int &l,const int &r)
{
	while(!lazy[k].empty())
	{
		if(lazy[k].front().first==1)
		{
			tree[k*2]=tree[k*2]*lazy[k].front().second%p;
			lazy[k*2].push(lazy[k].front());
			tree[k*2+1]=tree[k*2+1]*lazy[k].front().second%p;
			lazy[k*2+1].push(lazy[k].front());
			lazy[k].pop();
		}
		else
		{
			int mid=(l+r)/2;
			tree[k*2]=(tree[k*2]+lazy[k].front().second*(mid-l+1)%p)%p;
			lazy[k*2].push(lazy[k].front());
			tree[k*2+1]=(tree[k*2+1]+lazy[k].front().second*(r-mid)%p)%p;
			lazy[k*2+1].push(lazy[k].front());
			lazy[k].pop();
		}
	}
}
void build(const int &k,const int &l,const int &r)
{
	if(l==r)
	{
		tree[k]=arr[l]%p;
		return;
	}
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	tree[k]=(tree[k*2]+tree[k*2+1])%p;
}
void modify(const int &k,const int &l,const int &r,const int &x,const int &y,const pair<int,long long> &op)
{
	if(x<=l&&r<=y)
	{
		if(op.first==1)
		{
			tree[k]=tree[k]*op.second%p;
			lazy[k].push(op);
		}
		else
		{
			tree[k]=(tree[k]+op.second*(r-l+1)%p)%p;
			lazy[k].push(op);
		}
		return;
	}
	pushdown(k,l,r);
	int mid=(l+r)/2;
	if(x<=mid)
		modify(k*2,l,mid,x,y,op);
	if(mid+1<=y)
		modify(k*2+1,mid+1,r,x,y,op);
	tree[k]=(tree[k*2]+tree[k*2+1])%p;
}
long long query(const int &k,const int &l,const int &r,const int &x,const int &y)
{
	if(x<=l&&r<=y)
		return tree[k];
	pushdown(k,l,r);
	int mid=(l+r)/2;
	long long sum=0;
	if(x<=mid)
		sum=(sum+query(k*2,l,mid,x,y))%p;
	if(mid+1<=y)
		sum=(sum+query(k*2+1,mid+1,r,x,y))%p;
	return sum;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%d %lld",&n,&p);
	for(int i=1;i<=n;i++)
		scanf("%lld",&arr[i]);
	build(1,1,n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
//		for(int j=1;j<=n;j++)
//			printf("%d ",query(1,1,n,j,j));
//		printf("\n");
		int op;
		scanf("%d",&op);
		if(op==1||op==2)
		{
			int x,y;
			long long c;
			scanf("%d %d %lld",&x,&y,&c);
			modify(1,1,n,x,y,make_pair(op,c));
		}
		else
		{
			int x,y;
			scanf("%d %d",&x,&y);
			printf("%lld\n",query(1,1,n,x,y));
		}
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

如上，我使用tree表示线段树各节点区域中数的和，lazy表示每个节点的懒标记，pair<int,long long>表示一个修改操作，first表示操作类型，second表示题面中的$c$

交上去全部MLE，但我自己算内存觉得应该没问题

R54520393