<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

给定长度为 $N$ 的数列 $A$，以及 $M$ 条指令，每条指令可能是以下两种之一：

1. 1 x y，查询区间 $\[x,y\]$ 中的最大连续子段和，即 $\\max\\limits_{x \\le l \\le r \\le y}${$\\sum\\limits^r_{i=l} A\[i\]$}。
2. 2 x y，把 $A\[x\]$ 改成 $y$。

对于每个查询指令，输出一个整数表示答案。

输入格式

第一行两个整数 $N,M$。

第二行 $N$ 个整数 $A\[i\]$。

接下来 $M$ 行每行 $3$ 个整数 $k,x,y$，$k=1$ 表示查询（此时如果 $x>y$，请交换 $x,y$），$k=2$ 表示修改。

输出格式

对于每个查询指令输出一个整数表示答案。

每个答案占一行。

数据范围

$N \\le 500000, M \\le 100000$,
$\-1000 \\le A\[i\] \\le 1000$

输入样例：

5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2

输出样例：

2
-1

思路

线段树经典题。

考虑由左右两个区间子区间$tl,tr$得到当前区间的最大子段和$ans$，则有
$ans=\max\lbrace$$tl$的最大子段和，$tr$的最大子段和，跨越区间中点的最大子段和$\rbrace$
$tl$的最大子段和$\&tr$的最大子段和递归求即可。
跨越中点的的最大子段和$=$tl右端点起的向左的最大子段和$+$tr左端点起的向右的最大子段和

所以线段树上每个节点维护四个信息：

1. $maxl$:左端点起的向右的最大子段和
2. $maxr$:右端点起的向左的最大子段和
3. $maxt$整个区间的最大子段和
4. $sum$:区间和

然后$pushup$时这四个信息都更新一下即可。

代码

#include <iostream>
using namespace std;
const int N = 500010;
int n,m;
int a[N];
struct Node {
    int l,r;
    int tmax,lmax,rmax,sum;
}tr[4 * N];
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 * 2],tr[u * 2 + 1]);
}
void build (int u,int l,int r) {
    if (l == r) tr[u] = {l,r,a[l],a[l],a[l],a[l]};
    else {
        tr[u].l = l,tr[u].r = r;
        int mid = l + r >> 1;
        build (u * 2,l,mid),build (u * 2 + 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] = {x,x,v,v,v,v};
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify (u * 2,x,v);
        else modify (u * 2 + 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];
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query (u * 2,l,r);
        if (l > mid) return query (u * 2 + 1,l,r);
        Node left = query (u * 2,l,r);
        Node right = query (u * 2 + 1,l,r);
        Node ans;
        pushup (ans,left,right);
        return ans;
    }
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    build (1,1,n);
    while (m--) {
        int x,l,r;
        cin >> x >> l >> r;
        if (x == 1) {
            if (l > r) swap (l,r);
            cout << query (1,l,r).tmax << endl;
        }
        else modify (1,l,r);
    }
    return 0;
}