C. 【例题3】公园遛狗

C. 【例题3】公园遛狗

我们对于每一个线段树的节点，维护几个值

\(sum\) 表示当前区间的区间和

\(ml\) 表示最大前缀和

\(mr\) 表示最大后缀和

\(ans\) 表示当前区间的最大子段和

接下来我们来判断如何上传答案

首先假定 \(tr_{ls}\) 和 \(tr_{rs}\) 已经做好了，然后考虑合并成 \(tr_p\) 的值

首先 \(tr_p.sum=tr_{ls}.sum+tr_{rs}.sum\) 这个就是直接合并大区间

然后 \(tr_p.ml=\max(tr_{ls}.ml,tr_{ls}.sum+tr_{rs}.ml)\)

\(tr_p.mr=\max(tr_{rs}.mr,tr_{rs}.sum+tr_{ls}.ml)\)

这个自行对照画图

\(tr_p.ans=\max(\max(tr_{ls}.ans,tr_{rs}.ans),tr_{ls}.mr+tr_{rs}.ml)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;

int n, m;
struct node
{
    int l, r;
    ll maxleft, maxright, sum, ans;
} tr[N];

void pushon(int p)
{
    tr[p].sum = tr[p * 2].sum + tr[p * 2 + 1].sum;
    tr[p].maxleft = max(tr[p * 2].maxleft, tr[p * 2].sum + tr[p * 2 + 1].maxleft);
    tr[p].maxright = max(tr[p * 2 + 1].maxright, tr[p * 2 + 1].sum + tr[p * 2].maxright);
    tr[p].ans = max(max(tr[p * 2].ans, tr[p * 2 + 1].ans), tr[p * 2].maxright + tr[p * 2 + 1].maxleft);
}

void build(int p, int l, int r)
{
    tr[p].l = l, tr[p].r = r;
    if (l == r)
    {
        cin >> tr[p].sum;
        tr[p].maxleft = tr[p].maxright = tr[p].ans = tr[p].sum;
        return;
    }
    int mid = (l + r) >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    pushon(p);
}

node ask(int p, int ql, int qr)
{
    if (ql <= tr[p].l && tr[p].r <= qr)
        return tr[p];
    int mid = (tr[p].l + tr[p].r) >> 1;
    if (qr <= mid)
        return ask(p * 2, ql, qr);
    else
    {
        if (ql > mid)
            return ask(p * 2 + 1, ql, qr);
        node t, a = ask(p * 2, ql, qr), b = ask(p * 2 + 1, ql, qr);
        t.maxleft = max(a.maxleft, a.sum + b.maxleft);
        t.maxright = max(b.maxright, a.maxright + b.sum);
        t.ans = max(max(a.ans, b.ans), a.maxright + b.maxleft);
        return t;
    }
}

void update(int p, int a, int x)
{
    if (tr[p].l == tr[p].r)
    {
        tr[p].maxleft = tr[p].maxright = tr[p].ans = tr[p].sum = x;
        return;
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    if (a <= mid)
        update(p * 2, a, x);
    else
        update(p * 2 + 1, a, x);
    pushon(p);
}

int main()
{
    cin >> n >> m;
    build(1, 1, n);
    while (m--)
    {
        int opt, x, y;
        cin >> opt >> x >> y;
        if (opt == 1)
        {
            if (x > y)
                swap(x, y);
            cout << ask(1, x, y).ans << endl;
        }
        else
            update(1, x, y);
    }
    return 0;
}