在建树的时候总是忘记pushup,于是决定就不pushup了,所有初始化交给modify
#include <bits/stdc++.h>
using namespace std;
const int M = 5 * 1e5 + 10;
int n, m;
int an[M];
struct Node {
int l, r, ans, rans, lans, sum;
} tr[M * 4];
void pushup(Node &u, Node &l, Node &r) {
u.ans = max(max(l.ans, r.ans), l.rans + r.lans);
u.sum = l.sum + r.sum;
u.rans = max(r.rans, r.sum + l.rans);
u.lans = max(l.lans, l.sum + r.lans);
}
void pushup(int u) {
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r) {
tr[u]={l,r};
if(l==r)
return;
int mid = l+r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
Node query(int u, int l, int r) {
if (l <= tr[u].l && r >= tr[u].r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) {
return query(u << 1, l, r);
}
if (l >= mid + 1) {
return query(u << 1 | 1, l, r);
}
auto a = query(u << 1, l, r);
auto b = query(u << 1 | 1, l, r);
Node res;
pushup(res, a, b);
return res;
}
void modify(int u, int a, int v) {
if (tr[u].l == a && tr[u].r == a) {
tr[u]={a,a,v,v,v,v};
} else {
int mid = tr[u].r + tr[u].l >> 1;
if (a <= mid)
modify(u << 1, a, v);
else
modify(u << 1 | 1, a, v);
pushup(u);
}
}
int main() {
cin >> n >> m;
build(1, 1, n);
for (int i = 1; i <= n; i++) {
cin >> an[i];
modify(1,i,an[i]);
}
while (m--) {
int k, a, b;
cin>>k>>a>>b;
if (k == 1) {
if (a > b)
swap(a, b);
cout << query(1, a, b).ans<<"\n";
} else {
modify(1, a, b);
}
}
}