题意：区间求区间内的连续最大值和进行点修改。思考如何转移状态方程用lsum来表示该区间内从左边开始的最大值，rsum为区间内从右边开始的最大值。sum为区间的和，而ans为区间内的最大值，
lsum可以由lc的lsum和lc.sum+rc.lsum得到，
而rsum可以由rc.rsum和rc.sum+lc.rsum得到，
而sum即为lc.sum+rc.sum，
而ans为lc.lsum和rc.rsum和lc.sum+rc.lsum和lc.rsum+rc.sum一个最大值，
查询的话查到的放到一个结构体里面最后返回结构体即可。
点击查看代码
#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>
#include <string.h>
#include <map>
#include <queue>
#include <list>
#include <cmath>
#include <iomanip>
#define int long long
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc u<<1
#define rc u<<1|1
#define gcd __gcd
#define double long double
#define endl "\n"
#define INF LLONG_MAX
#define mod 1000000007
#define N 500005
const double PI = 3.14159265358979323846;
using namespace std;
int n, m,a[N];
struct Node {int l, r, lsum, rsum, ans, sum;}tr[N*4];
void pushup(int u)
{
tr[u].sum = tr[lc].sum + tr[rc].sum;
tr[u].ans = max({ tr[lc].ans,tr[rc].ans,tr[lc].rsum + tr[rc].lsum });
tr[u].lsum = max(tr[lc].lsum, tr[lc].sum + tr[rc].lsum);
tr[u].rsum = max({ tr[rc].rsum , tr[rc].sum + tr[lc].rsum});
}
void build(int u, int l, int r)
{
tr[u] = { l,r,a[l],a[l],a[l],a[l] };
if (l == r)return;
int mid = l + r >> 1;
build(lc, l, mid); build(rc, mid + 1, r);
pushup(u);
}
void change(int u, int pos, int d)
{
if (tr[u].l == tr[u].r)
{
tr[u].sum = tr[u].lsum = tr[u].rsum = tr[u].ans = d;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if (pos <= mid)change(lc, pos, d);
else change(rc, pos, d);
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 >> 1,cnt=0;
cnt += (l <= mid) + (r > mid);
if (l <= mid && cnt == 1)return query(lc, l, r);
if (r > mid && cnt == 1)return query(rc, l, r);
Node cur, a, b;
a = query(lc, l, r); b = query(rc, l, r);;
cur.sum = a.sum + b.sum;
cur.ans = max({ a.ans,b.ans,a.rsum + b.lsum });
cur.lsum = max({ a.lsum,a.sum + b.lsum });
cur.rsum = { max(b.rsum,b.sum + a.rsum) };
return cur;
}
signed main()
{
ios;
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> a[i];
build(1, 1, n);
while (m--)
{
int op; cin >> op;
if (op == 1)
{
int l, r; cin >> l >> r;
if (l > r)swap(l, r);
Node ans = query(1, l, r);
cout << ans.ans << endl;
}
else
{
int p, s; cin >> p >> s;
change(1,p,s);
}
}
return 0;
}