rt

题目

代码如下

#include <iostream>

using namespace std;

const int N = 5e5 + 5;

int n, m;

int a[N];

struct node {
    int l, r;
    
    int tmax, lmax, rmax, sum;
} tr[N << 2];

void pushup(node &u, node &l, node &r) {
    u.sum = l.sum + r.sum;
    u.lmax = max (l.lmax, l.sum + r.lmax);
    u.rmax = max (r.rmax, r.sum + l.rmax);
    u.tmax = max (max(l.tmax, r.tmax), l.rmax + r.lmax);
}

void pushup(int u) {
    pushup(tr[u],  tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
    if (l == r)
        tr[u] = (node){l, r, a[l], a[l], a[l], a[l]};
    else {
        tr[u].l = l, tr[u].r = r;
        
        int mid = (l + r) / 2;
        
        build (u << 1, l, mid), build (u << 1 | 1, mid + 1, r);
        
        pushup (u);
    }
}

int modify(int u, int x, int v) {
    if (tr[u].l == x && tr[u].r == x)
        tr[u] = (node){x, x, v, v, v, v};
    else {
        int mid = (tr[u].l + tr[u].r) / 2;
        
        if (x <= mid)
            modify(u << 1, x, v);
        
        else
            modify(u << 1 | 1, x, v);
            
        pushup (u);
    }
}

node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u];
    
    int mid = (tr[u].l + tr[u].r) / 2;
    
    if (r <= mid)
        return query(u << 1, l, r);
        
    if (l > mid)
        return query(u << 1 | 1, l, r);
    
    node L = query (u << 1, l, r), R = query (u << 1 | 1, l, r), ans;
    
    pushup(ans, L, R);
    
    return ans;
}

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; ++ i)
        cin >> a[i];
    
    build(1, 1, n);
    
    while (m --) {
        int op, l, r;
        
        cin >> op >> l >> r;
        
        if (op == 1) {
            if (l > r)
                swap(l, r);
            
            cout << query(1, l, r).tmax << "\n";
        }
        else
            modify(1, l, r);
    }
    
    return 0;
}