萌新把线段树全忘了,求调
查看原帖
萌新把线段树全忘了,求调
1327843
如履薄冰楼主2025/6/19 22:12
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int n, q, m, a[maxn * 4], tree[maxn * 4], lztp[maxn * 4], lztm[maxn * 4];
int ls(int x)
{
	return x * 2;
}
int rs(int x)
{
	return x * 2 + 1;
}
int pu(int x)
{
	tree[x] = tree[ls(x)] + tree[rs(x)];
}
void add(int cur, int l, int r, int p)
{
	lztp[cur] = p;
	int len = r - l + 1;
	tree[cur] = len * p % m;
}
void mul(int cur, int l, int r, int mul)
{
	lztm[cur] = mul;
	int len = r - l + 1;
	len %= m;
	tree[cur] %= m;
	tree[cur] *= len;
	tree[cur] %= m;
}
void pdp(int cur, int l, int r)
{
	if (lztp[cur] == 0)
	{
		return;
	}
	int mid = (l + r) / 2;
	add(ls(cur), l, mid, lztp[cur]);
	add(rs(cur), mid + 1, r, lztp[cur]);
	lztp[cur] = 0;
}
void pdm(int cur, int l, int r)
{
	if (lztm[cur] == 0)
	{
		return;
	}
	int mid = (l + r) / 2;
	mul(ls(cur), l, mid, lztm[cur]);
	mul(rs(cur), mid + 1, r, lztm[cur]);
	lztm[cur] = 0;
}
void maket(int cur, int l, int r)
{
	lztp[cur] = 0;
	lztm[cur] = 0;
	if (l == r)
	{
		tree[cur] = a[l];
		return;
	}
	int mid = (l + r) / 2;
	maket(ls(cur), l, mid);
	maket(rs(cur), mid + 1, r);
	pu(cur);
}
int query(int cur, int l, int r, int L, int R)
{
	if (L <= l && R >= r)
	{
		return tree[cur];
	}
	pdp(cur, l, r);
	int mid = (l + r) / 2, ret = 0;
	if (L <= mid)
	{
		ret += query(ls(cur), l, mid, L, R); 
	}
	if (R >= mid + 1)
	{
		ret += query(rs(cur), mid + 1, r, L, R);
	}
	return ret;
}
void update1(int cur, int l, int r, int L, int R, int v)
{
	if (L <= l && R >= r)
	{
		add(cur, l, r, v);
	}
	pdp(cur, l, r);
	int mid = (l + r) / 2;
	if (L <= mid)
	{
		update1(ls(cur), l, mid, L, R, v);
	}
	else
	{
		update1(rs(cur), mid + 1, r, L, R, v);
	}
	pu(cur);
	return;
}
void update2(int cur, int l, int r, int L, int R, int v)
{
	if (L <= l && R >= r)
	{
		mul(cur, l, r, v);
	}
	pdm(cur, l, r);
	int mid = (l + r) / 2;
	if (L <= mid)
	{
		update2(ls(cur), l, mid, L, R, v);
	}
	else
	{
		update2(rs(cur), mid + 1, r, L, R, v);
	}
	pu(cur);
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> q >> m;
	for (int i = 1; i <= n; ++ i)
	{
		cin >> a[i];
	}
	maket(1, 1, n);
	while (q --)
	{
		int op;
		cin >> op;
		if (op == 1)
		{
			int x, y, k;
			cin >> x >> y >> k;
			update2(1, 1, n, x, y, k);
		}
		else if (op == 2)
		{
			int x, y, k;
			cin >> x >> y >> k;
			update1(1, 1, n, x, y, k);
		}
		else
		{
			int x, y;
			cin >> x >> y;
			cout << query(1, 1, n, x, y) % m << endl;
		}
	}
	return 0;
} 
2025/6/19 22:12
加载中...