线段树2 代码求条

#include <bits/stdc++.h>
#define int long long 
using namespace std;
long long s[4010000], tag[4010000], tag2[4010000];
int a[1010000];
int n, q, qll, qrr, op, val, p;
int read()
{
	char c = getchar();
	int res = 0, bj = 1;
	while (c < '0' || c > '9')
	{
		if (c == '-')	bj = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')	res = res * 10 + c - 48, c = getchar();
	return res * bj;
}
void pushup(int k)
{
	int l = k << 1, r = k << 1 | 1;
	s[k] = (s[l] + s[r]) % p;
}
void upd(int k, int l, int r, int v, int type)
{
	if (type == 1)
		s[k] += (r - l + 1)	* v, s[k] %= p, tag[k] += v;
	if (type == 2)
		s[k] *= v, s[k] %= p, tag2[k] += v;
}
void pushdown(int k, int l, int r, int mid)
{
	int lson = k << 1, rson = k << 1 | 1;
	if (tag[k])
	{
		upd(lson, l, mid, tag[k], 1);
		upd(rson, mid + 1, r, tag[k], 1);
		tag[k] = 0;
	}
	if (tag2[k])
	{
		upd(lson, l, mid, tag2[k], 2);
		upd(rson, mid + 1, r, tag2[k], 2);
		tag2[k] = 0;
	}
}
void update(int k, int l, int r, int ql, int qr, int v, int type)
{
	if (ql <= l && r <= qr)	
	{
		upd(k, l, r, v, type);
		return;
	}
	int mid = (l + r) >> 1;
	pushdown (k, l, r, mid);
	if (ql <= mid)	update(k << 1, l, mid, ql, qr, v, type);
	if (mid < qr) 	update(k << 1 | 1, mid + 1, r, ql, qr, v, type);
	pushup(k);
}
void Build(int k, int l, int r)
{
	if (l == r)	
	{
		s[k] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	Build (k << 1, l, mid);
	Build (k << 1 | 1, mid + 1, r);
	pushup(k); 
}
long long ask(int k, int l, int r, int ql, int qr)
{
	if (ql <= l && r <= qr)	return s[k];
	long long mid = (l + r) >> 1, sum = 0;
	pushdown (k, l, r, mid);
	if (ql <= mid)	sum += ask(k << 1, l, mid, ql, qr) % p;
	if (mid < qr) 	sum += ask(k << 1 | 1, mid + 1, r, ql, qr) % p;
	return sum;
 } 
signed main()
{
	n = read(), q = read(), p = read();
	for (int i = 1; i <= n; i++)	a[i] = read();
	Build (1, 1, n);
	for (int i = 1; i <= q; i++)
	{	
		op = read(), qll = read(), qrr = read();
		if (op == 1)
		{
			val = read();
			update (1, 1, n, qll, qrr, val, 2);
		}
		if (op == 2)
		{
			val = read();
			update (1, 1, n, qll, qrr, val, 1);
		}
		if (op == 3)
			printf("%lld\n", ask(1, 1, n, qll, qrr) % p);
	}
	return 0;
}