lgP4513 小白逛公园

有n个公园，小白对第i个公园的评分为A[i]，有m次操作：

• 1 a b 表示在[a,b]范围内选择一段连续的公园遛狗；
• 2 a b 表示小白对公园a的评分修改为b；

对于操作1，输出可以取得的最大评分。

分析：线段树维护区间子段和。

#include <bits/stdc++.h>
using llong = long long;

const int inf = 1e9;

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree():n(0) {}
    SegmentTree(int _n, Info v = Info()) {
        init(_n, v);
    }
    void init(int _n, Info v = Info()) {
        init(std::vector<Info>(_n, v));
    }
    template<class T>
    SegmentTree(std::vector<T> v) {
        init(v);
    }
    template<class T>
    void init(std::vector<T> v) {
        n = v.size();
        info.assign(4 << std::__lg(n), Info());
        std::function<void(int,int,int)> build = [&](int x, int l, int r) {
            if (l + 1 == r) {
                info[x] = v[l];
                return;
            }
            int m = (l + r) / 2;
            build(2*x+1, l, m);
            build(2*x+2, m, r);
            pushup(x);
        };
        build(0, 0, n);
    }
    void pushup(int x) {
        info[x] = info[2*x+1] + info[2*x+2];
    }
    void assign(int x, int l, int r, int p, const Info &v) {
        if (l + 1 == r) {
            info[x] = v;
            return;
        }
        int m = (l + r) / 2;
        if (p < m) {
            assign(2*x+1, l, m, p, v);
        } else {
            assign(2*x+2, m, r, p, v);
        }
        pushup(x);
    }
    void assign(int p, const Info &v) {
        assign(0, 0, n, p, v);
    }
    void add(int x, int l, int r, int p, const Info &v) {
        if (l + 1 == r) {
            info[x] += v;
            return;
        }
        int m = (l + r) / 2;
        if (p < m) {
            add(2*x+1, l, m, p, v);
        } else {
            add(2*x+2, m, r, p, v);
        }
        pushup(x);
    }
    void add(int p, const Info &v) {
        add(0, 0, n, p, v);
    }
    Info rangeQuery(int x, int l, int r, int L, int R) {
        if (R <= l || r <= L) {
            return Info();
        }
        if (L <= l && r <= R) {
            return info[x];
        }
        int m = (l + r) / 2;
        return rangeQuery(2*x+1, l, m, L, R) + rangeQuery(2*x+2, m, r, L, R);
    }
    Info rangeQuery(int L, int R) {
        return rangeQuery(0, 0, n, L, R);
    }
    template<class F>
    int findFirst(int x, int l, int r, int L, int R, F pred) {
        if (R <= l || r <= L || !pred(info[x])) {
            return -1;
        }
        if (l + 1 == r) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findFirst(2*x+1, l, m, L, R, pred);
        if (res == -1) {
            res = findFirst(2*x+2, m, r, L, R, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int L, int R, F pred) {
        return findFirst(0, 0, n, L, R, pred);
    }
    template<class F>
    int findLast(int x, int l, int r, int L, int R, F pred) {
        if (R <= l || r <= L || !pred(info[x])) {
            return -1;
        }
        if (l + 1 == r) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findLast(2*x+2, m, r, L, R, pred);
        if (res == -1) {
            res = findLast(2*x+1, l, m, L, R, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int L, int R, F pred) {
        return findLast(0, 0, n, L, R, pred);
    }
    void print(int x, int l, int r) {
        std::cerr << x << "(" << l << "," << r << "): " << info[x] << "\n";
        if (l + 1 < r) {
            int m = (l+r) / 2;
            print(2*x+1, l, m);
            print(2*x+2, m, r);
        }
    }
    void print() {
        std::cerr << "--------------------------------\n";
        print(0, 0, n);
    }
};

struct Info {
    int pre;
    int max;
    int suf;
    int sum;
    Info(int s=-inf) {
        pre = max = suf = sum = s;
    }
    friend Info operator+(const Info &a, const Info &b) {
        if (a.max == -inf) return b;
        if (b.max == -inf) return a;
        Info ans;
        ans.pre = std::max(a.pre, a.sum + b.pre);
        ans.suf = std::max(b.suf, a.suf + b.sum);
        ans.sum = a.sum + b.sum;
        ans.max = std::max({a.max, b.max, a.suf + b.pre});
        return ans;
    }
    friend std::ostream& operator<<(std::ostream &out, Info &info) {
        out << "info:(" << ")";
        return out;
    }
};

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> A(n);
    for (int i = 0; i < n; i++) {
        std::cin >> A[i];
    }
    SegmentTree<Info> tr(A);
    for (int i = 0; i < m; i++) {
        int k, a, b;
        std::cin >> k >> a >> b;
        if (k == 1) {
            if (a > b) std::swap(a, b);
            std::cout << tr.rangeQuery(a-1, b).max << "\n";
        } else if (k == 2) {
            tr.assign(a-1, b);
        }
    }
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}