|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int N = 500010;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
int n, m;
|
|
|
|
|
|
// 线段树
|
|
|
#define int long long
|
|
|
#define ls (u << 1)
|
|
|
#define rs (u << 1 | 1)
|
|
|
#define mid ((l + r) >> 1)
|
|
|
struct Node {
|
|
|
int l, r; // 区间范围
|
|
|
int sum; // 区间和
|
|
|
int lx; // 左后缀最大和
|
|
|
int rx; // 右前缀最大和
|
|
|
int mx; // 整体最大和
|
|
|
} tr[N << 2];
|
|
|
|
|
|
void pushup(int u) {
|
|
|
tr[u].sum = tr[ls].sum + tr[rs].sum; // 区间和
|
|
|
tr[u].lx = max(tr[ls].lx, tr[ls].sum + tr[rs].lx); // 左端区间和+右端前缀最大和
|
|
|
tr[u].rx = max(tr[rs].rx, tr[rs].sum + tr[ls].rx); // 右端区间和+左端后缀最大和
|
|
|
tr[u].mx = max({tr[ls].mx, tr[rs].mx, tr[ls].rx + tr[rs].lx}); // 三者取max
|
|
|
}
|
|
|
|
|
|
// 构建
|
|
|
void build(int u, int l, int r) {
|
|
|
tr[u].l = l, tr[u].r = r;
|
|
|
if (l == r) {
|
|
|
int x;
|
|
|
cin >> x;
|
|
|
tr[u].sum = tr[u].lx = tr[u].rx = tr[u].mx = x;
|
|
|
return;
|
|
|
}
|
|
|
build(ls, l, mid), build(rs, mid + 1, r);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
// 在以u节点为根的子树中，将位置x的值修改为v
|
|
|
void change(int u, int x, int v) {
|
|
|
int l = tr[u].l, r = tr[u].r;
|
|
|
if (l == r) { // 叶节点
|
|
|
tr[u].lx = tr[u].rx = tr[u].mx = tr[u].sum = v;
|
|
|
return;
|
|
|
}
|
|
|
if (x <= mid)
|
|
|
change(ls, x, v);
|
|
|
else
|
|
|
change(rs, x, v);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
// 查询
|
|
|
Node query(int u, int L, int R) {
|
|
|
int l = tr[u].l, r = tr[u].r;
|
|
|
if (l > R || r < L) return {0, 0, -INF, -INF, -INF, -INF}; // 如果查询区间与当前区间无交集，则返回空
|
|
|
if (l >= L && r <= R) return tr[u]; // 如果完整覆盖命中，则返回tr[u]
|
|
|
|
|
|
Node b;
|
|
|
Node lc = query(ls, L, R), rc = query(rs, L, R);
|
|
|
b.sum = lc.sum + rc.sum; // 区间和
|
|
|
b.lx = max(lc.lx, lc.sum + rc.lx); // 左端区间和+右端前缀最大和
|
|
|
b.rx = max(rc.rx, rc.sum + lc.rx); // 右端区间和+左端后缀最大和
|
|
|
b.mx = max({lc.mx, rc.mx, lc.rx + rc.lx}); // 三者取max
|
|
|
return b;
|
|
|
}
|
|
|
|
|
|
signed main() {
|
|
|
// 加快读入
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
|
|
|
cin >> n >> m;
|
|
|
|
|
|
build(1, 1, n);
|
|
|
|
|
|
int op, l, r;
|
|
|
while (m--) {
|
|
|
cin >> op >> l >> r;
|
|
|
if (op == 1) {
|
|
|
if (l > r) swap(l, r);
|
|
|
printf("%d\n", query(1, l, r).mx);
|
|
|
} else
|
|
|
change(1, l, r);
|
|
|
}
|
|
|
return 0;
|
|
|
} |
