https://www.luogu.com.cn/problem/CF438D

线段树第 $39$ 个点 $wa$。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 3e5 + 5;
ll n, m, w[N], mod;

struct Node
{
	ll l, r, sum, maxn;
};

Node tree[N << 2];

inline void push_up(ll u)
{
	tree[u].sum = tree[u << 1].sum + tree[u << 1 | 1].sum;
	tree[u].maxn = max(tree[u << 1].maxn, tree[u << 1 | 1].maxn);
}

inline void build(ll u, ll l, ll r)
{
	tree[u].l = l;
	tree[u].r = r;
	if (l == r) tree[u].sum = tree[u].maxn = w[r];
	else
	{
		int mid = (l + r) >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		push_up(u);
	}
}

inline void modify1(ll u, ll x, ll v)
{
	if (tree[u].l == x && tree[u].r == x) tree[u].sum = v, tree[u].maxn = v;
	else
	{
		int mid = (tree[u].l + tree[u].r) >> 1;
		if (x <= mid) modify1(u << 1, x, v);
		else modify1(u << 1 | 1, x, v);
		push_up(u);
	}
}

inline void modify2(ll u, ll l, ll r)
{
	if (tree[u].l >= l && tree[u].r <= r && tree[u].sum < mod) return;
	if (tree[u].l >= l && tree[u].r <= r && tree[u].l == tree[u].r)
	{
		tree[u].sum %= mod;
		tree[u].maxn %= mod;
		return;
	}
	int mid = (tree[u].l + tree[u].r) >> 1;
	if (l <= mid) modify2(u << 1, l, r);
	if (r > mid) modify2(u << 1 | 1, l, r);
	push_up(u);
}

inline int query(ll u, ll l, ll r)
{
	if (tree[u].l >= l && tree[u].r <= r) return tree[u].sum;
	int mid = (tree[u].l + tree[u].r) >> 1, ans = 0;
	if (l <= mid) ans += query(u << 1, l, r);
	if (r > mid) ans += query(u << 1 | 1, l, r);
	return ans;
}

int main()
{
	scanf("%lld %lld", &n, &m);
	for (register int i = 1; i <= n; i++) scanf("%lld", &w[i]);
	build(1, 1, n);
	while (m--)
	{
		int x;
		scanf("%lld", &x);
		if (x == 1)
		{
			int l, r;
			scanf("%lld %lld", &l, &r);
			printf("%lld\n", query(1, l, r));
		}
		else if (x == 2)
		{
			int x, y;
			scanf("%lld %lld %lld", &x, &y, &mod);
			modify2(1, x, y);
		}
		else
		{
			int x, y;
			scanf("%lld %lld", &x, &y);
			modify1(1, x, y);
		}
	}
	return 0;
}