Noic seg merge.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int n, q, a[maxn];
struct no{
    ll seg, pref, suf, sum;
    no(){
        seg = pref = suf = sum = 0;
    }
    no(ll v){
        sum = v;
        v = max(v, 0LL);
        seg = pref = suf = v;
    }
}tree[4*maxn];
no join(no a, no b){
    no ans = 0;
    ans.seg = max({a.seg, b.seg, a.suf + b.pref});
    ans.pref = max({a.pref, a.sum + b.pref});
    ans.suf = max({b.suf, b.sum + a.suf});
    ans.sum = a.sum + b.sum;
    return ans;
}
void build(int node, int l, int r){
    if(l == r){
        tree[node] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(2*node, l, mid), build(2*node+1, mid+1, r);
    tree[node] = join(tree[2*node], tree[2*node+1]);
}
void update(int node, int tl, int tr, int pos, int val){
    if(tl == tr){
        a[pos] = val;
        tree[node] = a[pos];
        return;
    }
    int mid = (tl + tr) >> 1;
    if(pos <= mid) update(2*node, tl, mid, pos, val);
    else update(2*node+1, mid+1, tr, pos, val);
    tree[node] = join(tree[2*node], tree[2*node+1]);
}
no query(int node, int tl, int tr, int l, int r){
    if(tl > r or tr < l) return 0;
    if(tl >= l and tr <= r) return tree[node];
    int mid = (tl + tr) >> 1;
    return join(query(2*node, tl, mid, l, r), query(2*node+1, mid+1, tr, l, r));
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    build(1, 1, n);
    cout << query(1, 1, n, 1, n).seg << "\n";
    while(q--){
        int i, v;
        cin >> i >> v;
        update(1, 1, n, i+1, v);
        cout << query(1, 1, n, 1, n).seg << "\n";
    }
    return 0;
}