P4513 小白逛公园

9 pts 求调

#include<bits/stdc++.h>
using namespace std;
//_______________________________________________________________________________________________________________________________________________________
const int N = 1000010;

struct tree{
	int l, r;//区间 
	long long sum;//区间和 
	long long all_max;//区间最大子段和
	long long left_max;//区间靠左最大子段和
	long long right_max;//区间靠右最大子段和
	
	int len(){return r - l + 1;}
};
int ls(int u){return u << 1;}
int rs(int u){return u << 1 | 1;}
int fa(int u){return u >> 1;}

long long w[N];
tree tr[N << 2];

void pushup(int u){
	tree &root = tr[u], &lson = tr[ls(u)], &rson = tr[rs(u)];
	root.sum = lson.sum + rson.sum;
	root.left_max = max(lson.left_max, lson.sum + rson.left_max);
	root.right_max = max(rson.right_max, rson.sum + lson.right_max);
	root.all_max = max(max(max(root.left_max, root.right_max), max(lson.all_max, rson.all_max)), lson.right_max + rson.left_max);
}

void build(int l, int r, int u = 1){
	if(l == r){
		tr[u] = {l, r, w[l], w[l], w[l], w[l]};
	}
	else{
		tr[u] = {l, r};
		int mid = l + r >> 1;
		build(l, mid, ls(u));
		build(mid + 1, r, rs(u));
		pushup(u);
	}
}

void change(int k, long long w, int u = 1){//k处修改为w 
	if(tr[u].l == tr[u].r){
		tr[u] = {tr[u].l, tr[u].r, w, w, w, w};
		return;
	}
	int mid = tr[u].l + tr[u].r >> 1;
	if(k <= mid) change(k, w, ls(u));
	else change(k, w, rs(u));
	pushup(u);
}

tree query(int l, int r, int u = 1){
	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(l, r, ls(u));//全在左儿子 
	else if(l > mid) return query(l, r, rs(u));//全在右儿子 
	else {//左右都访问 
		tree lson = query(l, r, ls(u)), rson = query(l, r, rs(u)), root;
		//下面合并
		root.left_max = max(lson.left_max, lson.sum + rson.left_max);
		root.right_max = max(rson.right_max, rson.sum + lson.right_max);
		root.all_max = max(max(root.left_max, root.right_max), max(lson.all_max, rson.all_max));
		return root;
	}
}

//_______________________________________________________________________________________________________________________________________________________

int n, m;

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%lld", &w[i]);
	build(1, n);
	
	for(int i = 1; i <= m; i++){
		int op, a, b;
		scanf("%d%d%d", &op, &a, &b);
		if(op == 1) printf("%lld\n", query(min(a, b), max(a, b)).all_max);
		if(op == 2) change(a, b);
	}
	return 0;
}