9pts only AC on#1 求条 马蜂良好

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define endl '\n'

const int N = 5e5 + 10, inf = 1e15;

int n, mod;
int a[N];

struct NOde {
	int sum, lmx, rmx, max;
} tree[N * 4];

void push_up(int p) {
	tree[p].sum = tree[p * 2].sum + tree[p * 2 + 1].sum;
	tree[p].lmx = max(tree[p * 2].lmx, tree[p * 2].sum + tree[p * 2 + 1].lmx);
	tree[p].rmx = max(tree[p * 2 + 1].rmx, tree[p * 2].rmx + tree[p * 2 + 1].sum);
	tree[p].max = max(max(tree[p * 2].lmx, tree[p * 2 + 1].rmx), tree[p * 2].rmx + tree[p * 2 + 1].lmx);
}

void build(int p, int l, int r) {
	if (l == r) {
		tree[p].sum = tree[p].lmx = tree[p].rmx = tree[p].max = a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(p * 2, l, mid);
	build(p * 2 + 1, mid + 1, r);
	push_up(p);
}

void update(int p, int l, int r, int id, int val) {
	if (id > r || id < l) return ;
	if (l == r) {
		tree[p].lmx = tree[p].max = tree[p].rmx = tree[p].sum = val;
		return;
	}
	int mid = (l + r) >> 1;
	update(p * 2, l, mid, id, val);
	update(p * 2 + 1, mid + 1, r, id, val);
	push_up(p);
}

NOde query(int p, int l, int r, int a, int b) {
	if (l >= a && r <= b) return tree[p];
	if (l > b || r < a) return {-inf, -inf, -inf, -inf};
	int mid = (l + r) >> 1;
	NOde x, y, ans;
	if (b <= mid) return query(p * 2, l, mid, a, b);
	if (a > mid) return query(p * 2 + 1, mid + 1, r, a, b);
	x = query(p * 2, l, mid, a, b);
	y = query(p * 2 + 1, mid + 1, r, a, b);
	ans.sum = x.sum + y.sum;
	ans.lmx = max(x.sum + y.lmx, x.lmx);
	ans.rmx = max(x.rmx + y.sum, y.rmx);
	ans.max = max(max(x.lmx, y.rmx), x.rmx + y.lmx);
	return ans;
}

signed main() {
//	freopen("test.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int q;
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	build(1, 1, n);
	while (q--) {
		int op;
		int a, b;
		cin >> op >> a >> b;
		if (op == 2) {
			update(1, 1, n, a, b);
		} else {
			if (a > b) swap(a, b);
			cout << query(1, 1, n, a, b).max << '\n';
		}
	}
}