题意:带修 求区间最大连续子段和

题解:我们需要维护的信息有 区间和 区间最大子段和 区间左连续最大子段和 区间右连续最大子段和

　　 然后模拟即可

 

#include 
      
       using namespace std;const int MAXN = 5e4 + 5;int n, m;int a[MAXN];struct node {    int sum, ssum, ls, rs;}E[MAXN << 2];void pushup(int rt) {    int lr = rt << 1;    int rr = rt << 1 | 1;    E[rt].ssum = E[lr].ssum + E[rr].ssum;    E[rt].sum = max(E[lr].sum, E[rr].sum);    E[rt].sum = max(E[rt].sum, E[lr].rs + E[rr].ls);    E[rt].ls = max(E[lr].ls, E[lr].ssum + E[rr].ls);    E[rt].rs = max(E[rr].rs, E[rr].ssum + E[lr].rs);}void build(int l, int r, int rt) {    if(l == r) {        E[rt].sum = a[l];        E[rt].ls = E[rt].rs = E[rt].ssum = a[l];        return;    }    int mid = l + r >> 1;    build(l, mid, rt << 1);    build(mid + 1, r, rt << 1 | 1);    pushup(rt);}void update(int k, int v, int l, int r, int rt) {    if(l == r) {        E[rt].ssum = E[rt].sum = E[rt].ls = E[rt].rs = v;        return;    }    int mid = l + r >> 1;    if(k <= mid) update(k, v, l, mid, rt << 1);    else update(k, v, mid + 1, r, rt << 1 | 1);    pushup(rt);}node query(int ql, int qr, int l, int r, int rt) {    if(ql <= l && qr >= r) return E[rt];    int mid = l + r >> 1;    if(qr <= mid) return query(ql, qr, l, mid, rt << 1);    if(ql > mid) return query(ql, qr, mid + 1, r, rt << 1 | 1);    node ll = query(ql, qr, l, mid, rt << 1);    node rr = query(ql, qr, mid + 1, r, rt << 1 | 1);    node res;    res.ssum = ll.ssum + rr.ssum;    res.sum = max(ll.sum, rr.sum);    res.sum = max(res.sum, ll.rs + rr.ls);    res.ls = max(ll.ls, ll.ssum + rr.ls);    res.rs = max(rr.rs, rr.ssum + ll.rs);    return res;}int main() {    scanf("%d", &n);    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);    build(1, n, 1);    scanf("%d", &m);    for(int i = 1; i <= m; i++) {        int opt, x, y;        scanf("%d%d%d", &opt, &x, &y);        if(opt == 1) printf("%d\n", query(x, y, 1, n, 1).sum);        else update(x, y, 1, n, 1);    }    return 0;}