思路：
因为有区间取模操作所以没法用标记下传；
我们发现，当一个数小于要取模的值时就可以放弃；
凭借这个来减少更新线段树的次数；
来，上代码：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define maxn 100005 #define ll long long struct TreeNodeType { ll l, r, mid, dis, max; }; struct TreeNodeType tree[maxn << 2]; ll n,m; inline void in(ll &now) { char Cget = getchar(); now = 0; while (Cget > '9' || Cget < '0') Cget = getchar(); while (Cget >= '0'&&Cget <= '9') { now = now * 10 + Cget - '0'; Cget = getchar(); } } void tree_build(ll now, ll l, ll r) { tree[now].l = l, tree[now].r = r; if (l == r) { in(tree[now].dis); tree[now].max = tree[now].dis; return; } tree[now].mid = l + r >> 1; tree_build(now << 1, l, tree[now].mid); tree_build(now << 1 | 1, tree[now].mid + 1, r); tree[now].dis = tree[now << 1].dis + tree[now << 1 | 1].dis; tree[now].max = max(tree[now << 1].max, tree[now << 1 | 1].max); } void tree_to(ll now, ll to,ll x) { if (tree[now].l == tree[now].r) { tree[now].dis = x; tree[now].max = x; return; } if (to <= tree[now].mid) tree_to(now << 1, to, x); else tree_to(now << 1 | 1, to, x); tree[now].dis = tree[now << 1].dis + tree[now << 1 | 1].dis; tree[now].max = max(tree[now << 1].max, tree[now << 1 | 1].max); } void tree_mod(ll now, ll l, ll r, ll x) { if (tree[now].max < x) return; if (tree[now].l >= l&&tree[now].r <= r) tree[now].dis %= x, tree[now].max %= x; if (tree[now].l == tree[now].r) return; if (l <= tree[now].mid) tree_mod(now << 1, l, r, x); if (r > tree[now].mid) tree_mod(now << 1|1, l, r, x); tree[now].dis = tree[now << 1].dis + tree[now << 1 | 1].dis; tree[now].max = max(tree[now << 1].max, tree[now << 1 | 1].max); //cout <<"^ "<< l << ' ' << r << ' ' << tree[now].dis << ' ' << tree[now].max << endl; } ll tree_query(ll now, ll l, ll r) { if (tree[now].l == l&&tree[now].r == r) return tree[now].dis; if (l > tree[now].mid) return tree_query(now << 1 | 1, l, r); else if (r <= tree[now].mid) return tree_query(now << 1, l, r); else return tree_query(now << 1, l, tree[now].mid) + tree_query(now << 1 | 1, tree[now].mid + 1, r); } int main() { in(n), in(m); tree_build(1, 1, n); ll op, u, v, x; for (; m--;) { in(op),in(u),in(v); if (op == 1) printf("%lld ", tree_query(1, u, v)); if (op == 2) in(x), tree_mod(1, u, v, x); if (op == 3) tree_to(1, u, v); } return 0; }