求调QwQ

这个是提交记录

我的结构体存了这些东西，不知道可不可行：

all -> 区间总和

sum -> 区间连续最大和

lsum -> 左连续区间最大和

rsum -> 右连续区间最大和

maxx -> 区间内单点最大值（这个是因为我把题目先看作可以不取任何节点的值，然后判断结果是否为零：为零就代表没选，所以输出maxx；否则输出sum）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int n, q, a[maxn];
#define half (l + r) >> 1
#define lc rt << 1
#define rc rt << 1 | 1
#define lson lc, l, mid
#define rson rc, mid + 1, r
#define QL lson, ql, qr
#define QR rson, ql, qr
#define QLx lson, qx, val
#define QRx rson, qx, val
struct Tree {
	int all, sum, lsum, rsum, maxx;
	Tree () {
		all = 0;
		sum = 0;
		lsum = 0;
		rsum = 0;
		maxx = 0;
	}
} tree[maxn << 2], tmp;
void pushup (int rt) {
	tree[rt].all = tree[lc].all + tree[rc].all;
	tree[rt].maxx = max(tree[lc].maxx, tree[rc].maxx);
	tree[rt].sum = max(tree[lc].sum, tree[rc].sum);
	tree[rt].sum = max(tree[rt].sum, tree[lc].rsum + tree[rc].lsum);
	tree[rt].sum = max(tree[rt].sum, tree[lc].lsum);
	tree[rt].sum = max(tree[rt].sum, tree[rc].rsum);
	tree[rt].lsum = tree[lc].lsum;
	tree[rt].rsum = tree[rc].rsum;
	if (tree[rt].lsum == tree[lc].all) tree[rt].lsum += tree[rc].lsum;
	if (tree[rt].rsum == tree[rc].all) tree[rt].rsum += tree[lc].rsum;
}
void build (int rt, int l, int r) {
	if (!(l ^ r)) {
		tree[rt].all = a[l];
		tree[rt].maxx = a[l];
		int val = max(a[l], 0);
		tree[rt].sum = val;
		tree[rt].lsum = val;
		tree[rt].rsum = val;
		return;
	}
	int mid = half;
	build (lson);
	build (rson);
	pushup (rt);
}
void update (int rt, int l, int r, int qx, int val) {
	if (!(l ^ r)) {
		tree[rt].all = tree[rt].maxx = val;
		tree[rt].sum = tree[rt].lsum = tree[rt].rsum = max(val, 0);
		return;
	}
	int mid = half;
	if (qx <= mid) update (QLx);
	else update (QRx);
	pushup (rt);
}
Tree query(int rt, int l, int r, int ql, int qr) {
	if (ql <= l && qr >= r) return tree[rt];
	int mid = half;
	if (qr <= mid) return query(QL);
	else if (ql > mid) return query(QR);
	else {
		Tree L = query(QL);
		Tree R = query(QR);
		Tree ans;
		ans.all = L.all + R.all;
		ans.maxx = max(L.maxx, R.maxx);
		ans.sum = max(L.sum, R.sum);
		ans.sum = max(ans.sum, L.rsum + R.lsum);
		ans.sum = max(ans.sum, L.lsum);
		ans.sum = max(ans.sum, R.rsum);
		ans.lsum = L.lsum;
		ans.rsum = R.rsum;
		if (ans.lsum == L.all) ans.lsum += R.lsum;
		if (ans.rsum == R.all) ans.rsum += L.rsum;
		return ans;
	}
}
int main () {
	scanf ("%d%d", &n, &q);
	for (int i = 1; i <= n; i ++) scanf ("%d", &a[i]);
	build (1, 1, n);
	for (int i = 1, op, l, r; i <= q; i ++) {
		scanf ("%d%d%d", &op, &l, &r);
		if (op & 1) {
			if (l > r) swap(l, r);
			tmp = query(1, 1, n, l, r);
			if (!tmp.sum) printf ("%d\n", tmp.maxx);
			else printf ("%d\n", tmp.sum);
		}
		else {
			update (1, 1, n, l, r);
		}
	}
	return 0;
}