线段树模板求调

#include<iostream>
#include<cmath>
#include<algorithm>
#define b0fitn for(int i=0;i<n;i++)
#define b1fitn for(int i=1;i<=n;i++)
using namespace std;

struct Node
{
	int sum = 0, tag1 = 0, tag2 = 1;
};

const int MAXN = 1e5+55;
int n, modb, op, t, g, c, m, nums[MAXN];
Node tree[MAXN*4];

inline int ls(int x) 
{
	return x >> 1;
}

inline int rs(int x)
{
	return (x >> 1) | 1;
}

void pushup(int p)
{
	tree[p].sum = (tree[ls(p)].sum + tree[rs(p)].sum) % modb;
}

void func(int l, int r, int p, int fa)
{
	tree[p].sum = (tree[p].sum * tree[fa].tag2 + tree[fa].tag1 * (r-l+1)) % modb;
	tree[p].tag1 = (tree[p].tag1 + tree[fa].tag1) % modb;
	tree[p].tag2 = (tree[p].tag2 * tree[fa].tag2) % modb;
}

void pushdown(int l, int r, int p)
{
	int mid = (l+r) / 2;
	func(l, mid, ls(p), p);
	func(mid+1, r, rs(p), p);
	tree[p].tag1 = 0, tree[p].tag2 = 1;
}

void build(int l, int r, int p)
{
	if(l == r)
	{
		tree[p].sum = (nums[l]) % modb;
		return;
	}
	int mid = (l+r) / 2;
	build(l, mid, ls(p));
	build(mid+1, r, rs(p));
	pushup(p);
}

int query(int x, int y, int l, int r, int p)
{
	if(x <= l && r <= y)
	{
		return tree[p].sum % modb;
	}
	int mid = (l+r) / 2, res = 0;
	pushdown(l, r, p);
	if(x <= mid) res += query(x, y, l, mid, ls(p));
	if(y > mid) res += query(x, y, mid+1, r, rs(p));
	pushup(p);
	return res;
}

void _plus(int x, int y, int k, int l, int r, int p)
{
	if(x <= l && r <= y)
	{
		tree[p].tag1 = (tree[p].tag1 + k) % modb;
		tree[p].sum = (tree[p].sum + k * (r-l+1)) % modb;
		return;
	}
	int mid = (l+r) / 2;
	pushdown(l, r, p);
	if(x <= mid) _plus(x, y, k, l, mid, ls(p));
	if(y > mid) _plus(x, y, k, mid+1, r, rs(p));
	pushup(p);
}

void multi(int x, int y, int k, int l, int r, int p)
{
	if(x <= l && r <= y)
	{
		tree[p].tag2 = (tree[p].tag2 * k) % modb;
		tree[p].tag1 = (tree[p].tag1 * k) % modb;
		tree[p].sum = (tree[p].sum * k) % modb;
		return;
	}
	int mid = (l+r) / 2;
	pushdown(l, r, p);
	if(x <= mid) multi(x, y, k, l, mid, ls(p));
	if(y > mid) multi(x, y, k, mid+1, r, rs(p));
	pushup(p);
}

void solve(int op)
{
	build(1, n, 1);
	if(op == 1)
	{
		cin >> t >> g >> c;
		multi(t, g, c, 1, n, 1);
	}
    if(op == 2)
	{
		cin >> t >> g >> c;
		_plus(t, g, c, 1, n, 1);
	}
    if(op == 3)
	{
		cin >> t >> g;
		cout << query(t, g, 1, n, 1) % modb << endl;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> modb;
	b1fitn cin >> nums[i];
	cin >> m;
	while(m--)
	{
		cin >> op;
		solve(op);
	}
	return 0;
}