变量解释

• linearTree：线段树
• tagAdd/tagMul：加乘懒标记

代码

#include <iostream>
#include <iso646.h>
using namespace std;
typedef int64_t ll;
const ll N = 1e5 + 10;
ll mod, linearTree[N << 2], tagAdd[N << 2], tagMul[N << 2];
inline ll leftSon(const ll &k) { return k << 1; }
inline ll rightSon(const ll &k) { return k << 1 | 1; }
inline void grab_sum(const ll &k)
{
	linearTree[k] = (linearTree[leftSon(k)] + linearTree[rightSon(k)]) % mod;
}
void build(const ll &ptr, const ll &lb, const ll &rb)
{
	tagMul[ptr] = 1;
	if (lb == rb)
	{
		cin >> linearTree[ptr];
		return;
	}
	ll mid = (lb + rb) >> 1;
	build(leftSon(ptr), lb, mid);
	build(rightSon(ptr), mid + 1, rb);
	grab_sum(ptr);
}
void push_tag(const ll &source, const ll &k, const ll &lb, const ll &rb)
{
	tagAdd[k] = (tagAdd[k] * tagAdd[source] % mod + tagAdd[source]) % mod;
	tagMul[k] = (tagMul[k] * tagMul[source]) % mod;
	linearTree[k] = (linearTree[k] * tagMul[source] % mod + tagAdd[source] * (rb - lb + 1)) % mod;
}
void push_node(const ll &ptr, const ll &leftBorder, const ll &rightBorder)
{
	ll mid = (leftBorder + rightBorder) >> 1;
	push_tag(ptr, leftSon(ptr), leftBorder, mid);
	push_tag(ptr, rightSon(ptr), mid + 1, rightBorder);
	tagAdd[ptr] = 0;
	tagMul[ptr] = 1;
}
void add(const ll &ptr, ll leftBorder, ll rightBorder, const ll &tlb, const ll &trb, const ll &val)
{
	if (leftBorder > trb or rightBorder < tlb)
		return;
	if (leftBorder >= tlb and rightBorder <= trb)
	{
		tagAdd[ptr] = (tagAdd[ptr] + val) % mod;
		linearTree[ptr] = (linearTree[ptr] + val * (rightBorder - leftBorder + 1)) % mod;
		return;
	}
	if(tagMul[ptr] != 1 or tagAdd[ptr])push_node(ptr, leftBorder, rightBorder);
	ll mid = (leftBorder + rightBorder) >> 1;
	if (tlb <= mid)
		add(leftSon(ptr), leftBorder, mid, tlb, trb, val);
	if (trb > mid)
		add(rightSon(ptr), mid + 1, rightBorder, tlb, trb, val);
	grab_sum(ptr);
}
void mul(const ll &ptr, ll leftBorder, ll rightBorder, const ll &tlb, const ll &trb, const ll &val)
{
	if (leftBorder > trb or rightBorder < tlb)
		return;
	if (leftBorder >= tlb and rightBorder <= trb)
	{
		tagMul[ptr] = (tagMul[ptr] * val) % mod;
		tagAdd[ptr] = (tagAdd[ptr] * val) % mod;
		linearTree[ptr] = (linearTree[ptr] * val) % mod;
		return;
	}
	if(tagMul[ptr] != 1 or tagAdd[ptr])push_node(ptr, leftBorder, rightBorder);
	ll mid = (leftBorder + rightBorder) >> 1;
	if (tlb <= mid)
		mul(leftSon(ptr), leftBorder, mid, tlb, trb, val);
	if (trb > mid)
		mul(rightSon(ptr), mid + 1, rightBorder, tlb, trb, val);
	grab_sum(ptr);
}
ll query(const ll &ptr, ll leftBorder, ll rightBorder, const ll &tlb, const ll &trb)
{
	if (leftBorder >= tlb and rightBorder <= trb)
	{
		return linearTree[ptr] % mod;
	}
	if (leftBorder == rightBorder)
		return 0;
	if(tagMul[ptr] != 1 or tagAdd[ptr])push_node(ptr, leftBorder, rightBorder);
	ll mid = (leftBorder + rightBorder) >> 1, ret = 0;
	if (tlb <= mid)
		ret = (ret + query(leftSon(ptr), leftBorder, mid, tlb, trb)) % mod;
	if (trb > mid)
		ret = (ret + query(rightSon(ptr), mid + 1, rightBorder, tlb, trb)) % mod;
	return ret%mod;
}
ll n, m, opt, t1, t2, t3;
int main()
{
	scanf("%lld%lld%lld", &n, &m, &mod);
	build(1,1,n);
	while (m--)
	{
		scanf("%lld%lld%lld", &opt, &t1, &t2);
		if (opt == 1)
		{
			scanf("%lld", &t3);
			mul(1, 1, n, t1, t2, t3);
		}
		if (opt == 2)
		{
			scanf("%lld", &t3);
			add(1, 1, n, t1, t2, t3);
		}
		if (opt == 3)
		{
			printf("%lld\n", query(1, 1, n, t1, t2));
		}
	}
}