传送门：P10516 数据结构

更佳的阅读体验：洛谷 P10516 题解

简要题意：维护两个序列 $a$ 和 $b$，要求支持区间加、单点赋值、区间查询。

对于这些操作，我们考虑使用线段树。

考虑操作一需要维护的信息。题目要求给 $a_i \times b_i \le k$ 的位置的 $a_i$ 和 $b_i$ 各加上 $t$，显然需要维护的是与 $a_i \times b_i$ 相关的信息。对于线段树上的节点，如果我们要给每个 $\le k$ 的区间都修改，那么要保证当前节点代表的区间也 $\le k$，这样才能够递归下去。

这时，我们就可以想到维护区间内 $a_i \times b_i$ 的最小值。这样，如果一个节点代表的区间的最小值 $\le k$，那么代表这个区间内一定有满足 $a_i \times b_i \le k$ 的子区间，即可递归进行修改。

操作二就是朴素的单点修改。

操作三为查询区间和。注意到，每次查询只关心 $a_i + b_i$ 是多少，而不关心 $a_i$ 和 $b_i$ 具体的值。因此，我们直接维护区间 $a_i + b_i$ 和即可。

这样，操作二就变为将位置 $i$ 的和修改为 $x + y$，积修改为 $x \times y$。

值得注意的是，在操作一中，$t = 0$ 时仍然进行修改将耗费大量的时间，因此还需要对这一情况进行特判。

#include <iostream>
#define ls(p) t[p].lson
#define rs(p) t[p].rson
#define mid (l + r >> 1)
using namespace std;
using ll = long long;

const int N = 1e5 + 10;
const ll INF = 1e18;
ll n, m, a[N], b[N], op, l, r, k, t, x, y, ans;
struct seg_tree {
    int rt[N << 1], tot;
    struct node {
        int lson, rson;
        ll sum, minprod;
    } t[N << 1];

    void pushup(int p) {
        t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
        t[p].minprod = min(t[ls(p)].minprod, t[rs(p)].minprod);
    }

    void build(int &p, int l, int r) {
        p = ++tot;
        t[p].minprod = INF;
        if (l == r) return t[p].sum = a[l] + b[l], t[p].minprod = a[l] * b[l], void();
        build(ls(p), l, mid);
        build(rs(p), mid + 1, r);
        pushup(p);
    }

    ll query(int p, int l, int r, int L, int R) {
        if (l > R || r < L) return 0;
        if (l >= L && r <= R) return t[p].sum;
        return query(ls(p), l, mid, L, R) + query(rs(p), mid + 1, r, L, R);
    }

    void update_add(int p, int l, int r, int L, int R, int k, int x) {
        if (l > R || r < L || t[p].minprod > k) return;
        if (l == r) return t[p].sum += (x << 1), t[p].minprod = (a[l] += x) * (b[l] += x), void();
        update_add(ls(p), l, mid, L, R, k, x);
        update_add(rs(p), mid + 1, r, L, R, k, x);
        pushup(p);
    }

    void update_assign(int p, int l, int r, int k, int x, int y) {
        if (l > k || r < k) return; 
        if (l == r) return t[p].sum = x + y, t[p].minprod = 1ll * x * y, void();
        update_assign(ls(p), l, mid, k, x, y);
        update_assign(rs(p), mid + 1, r, k, x, y);
        pushup(p);
    }
} tree;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    tree.build(tree.rt[1], 1, n);
    while (m--) {
        cin >> op;
        if (op == 1) {
            cin >> l >> r >> k >> t;
            if (!t) continue;
            tree.update_add(tree.rt[1], 1, n, l, r, k, t);
        } else if (op == 2) cin >> l >> x >> y, a[l] = x, b[l] = y, tree.update_assign(tree.rt[1], 1, n, l, x, y);
        else cin >> l >> r, cout << tree.query(tree.rt[1], 1, n, l, r) << '\n';
    } return 0;
}