求助分块

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int x = 0,p = 1;
	char c = getchar();
	while(c > '9' || c < '0')	p = c == '-' ? -1 : 1,c = getchar();
	while(c >= '0' && c <= '9')	x = (x << 1) + (x << 3) + (c ^ 48),c = getchar();
	return p * x;
}
template<typename _Tp> void _write(_Tp x) { if(x > 9) _write(x / 10); putchar(x % 10 | 48); }
template<typename _Tp> void write(_Tp x) { if(x < 0) putchar('-'),x = -x; _write(x); }
template<typename _Tp> void writeln(_Tp x) { write(x); puts(""); }
#define mod (long long)(1e9 + 7)
const int N = 1e5 + 10;
const int M = 1e3 + 10;
int n,m,q,L,a[N],b[N],l[M],r[M],len[M],bs[M];
struct lazytag { int k,b; };
lazytag tag[M],t;
inline void init() { t = (lazytag){1,0}; }
inline lazytag operator + (lazytag x,int k)
{
	(x.b += k) %= m;
	return x;
}
inline lazytag operator * (lazytag x,int k)
{
	(x.k *= k) %= m; (x.b *= k) %= m;
	return x;
}
inline int calc(int y,lazytag x) { return (x.k * y % m + x.b) % m; }
inline void pushdown(int p)
{
	if(tag[p].k == t.k && tag[p].b == t.b)	return;
	for(int i = l[p];i <= r[p];i++)
	{
		bs[p] -= a[i];
		bs[p] %= m;
		a[i] = calc(a[i],tag[p]);
		bs[p] += a[i];
		bs[p] %= m;
		(bs[p] += m) %= m;
	}
	tag[p] = t;
}
inline void add(int L,int R,int k)
{
	if(b[L] != b[R])
	{
		pushdown(b[L]); pushdown(b[R]);
		for(int i = L;b[L] == b[i];i++)	(a[i] += k) %= m,(bs[b[i]] += k) %= m;
		for(int i = R;b[R] == b[i];i--)	(a[i] += k) %= m,(bs[b[i]] += k) %= m;
		for(int i = b[L] + 1;i <= b[R] - 1;i++)	tag[i] = tag[i] + k;
	}
	else
	{
		pushdown(b[L]);
		for(int i = L;i <= R;i++)	(a[i] += k) %= m,(bs[b[i]] += k) %= m;
	}
}
inline void mul(int L,int R,int k)
{
	if(b[L] != b[R])
	{
		pushdown(b[L]); pushdown(b[R]);
		for(int i = L;b[L] == b[i];i++)	bs[b[i]] -= a[i],(a[i] *= k) %= m,(bs[b[i]] += a[i]) %= m,(bs[b[i]] += m) %= m;
		for(int i = R;b[R] == b[i];i--)	bs[b[i]] -= a[i],(a[i] *= k) %= m,(bs[b[i]] += a[i]) %= m,(bs[b[i]] += m) %= m;
		for(int i = b[L] + 1;i <= b[R] - 1;i++)	tag[i] = tag[i] * k;
	}
	else
	{
		pushdown(b[L]);
		for(int i = L;i <= R;i++)	bs[b[i]] -= a[i],(a[i] *= k) %= m,(bs[b[i]] += a[i]) %= m,(bs[b[i]] += m) %= m;
	}
}
inline int query(int L,int R)
{
	int ans = 0;
	if(b[L] != b[R])
	{
		pushdown(b[L]); pushdown(b[R]);
		for(int i = L;b[L] == b[i];i++)	(ans += a[i]) %= m;
		for(int i = R;b[R] == b[i];i--)	(ans += a[i]) %= m;
		for(int i = b[L] + 1;i <= b[R] - 1;i++)	(ans += bs[i] * tag[i].k % m + tag[i].b * len[i] % m) %= m;
	}
	else
	{
		pushdown(b[L]);
		for(int i = L;i <= R;i++)	(ans += a[i]) %= m;
	}
	return ans;
}
signed main()
{
	n = read(); q = read(); m = read(); L = sqrt(n);
	init();
	for(int i = 1;i <= n;i++)	a[i] = read();
	for(int i = 1;i <= n;i++)	b[i] = (i - 1) / L + 1;
	for(int i = 1;i <= n;i++)	(bs[b[i]] += a[i]) %= m;
	memset(l,0x3f,sizeof(l));
	for(int i = 1;i <= n;i++)	l[b[i]] = min(l[b[i]],i);
	for(int i = 1;i <= n;i++)	r[b[i]] = i;
	for(int i = 1;i <= n;i++)	len[b[i]] = r[b[i]] - l[b[i]] + 1;
	for(int i = 1;i <= b[n];i++)	tag[i] = t;
	int op,x,y,k;
	while(q--)
	{
		op = read(); x = read(); y = read();
		if(op == 1)
		{
			k = read();
			mul(x,y,k);
		}
		else if(op == 2)
		{
			k = read();
			add(x,y,k);
		}
		else	writeln(query(x,y)); 
	}
	return 0;
}