关同步是cin cout党的胜利
#include<bits/stdc++.h>
using namespace std;
int n, m, t, x, y;
const int N = 5e5 + 10;
int w[N];
struct Node{
int l, r;
int tmax, lmax, rmax, sum;
} tr[4 * N];
void pushup(Node & u, Node & l, Node & r)
{
u.tmax = max(l.tmax, max(r.tmax, l.rmax + r.lmax));
u.sum = l.sum + r.sum;
u.lmax = max(l.lmax, l.sum + r.lmax);
u.rmax = max(r.rmax, r.sum + l.rmax);
}
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] = {l, r, w[l], w[l], w[l], w[l]};
else{
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
tr[u] = {l, r};
pushup(u);
}
}
Node query(int u, int l, int r)
{
if(l <= tr[u].l && tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query(u << 1, l, r);
else if(mid < l) return query(u << 1 | 1, l, r);
else
{
Node res, left = query(u << 1, l, r), right = query(u << 1 | 1, l, r);
pushup(res, left, right);
return res;
}
}
void modify(int u, int x, int v)
{
if(tr[u].l == tr[u].r) tr[u] = {x, x, v, v, v, v};
else if(x <= tr[u].l + tr[u].r >> 1) modify(u << 1, x, v), pushup(u);
else modify(u << 1 | 1, x, v), pushup(u);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> w[i];
build(1, 1, n);
for(int i = 1; i <= m; i ++)
{
cin >> t >> x >> y;
if(t == 1)
cout << query(1, min(x, y), max(x, y)).tmax << endl;
else modify(1, x, y);
}
}