luoguP4513 小白逛公园

大意

长度为n的序列，m次操作

单点修改，求区间和最大子段

n≤5e5, m≤1e5

分析

画图分析，几种情况
[a,b]中最大子段和 =
max( [左子树的最大子段和，右子树的最大子段和，过中间点且不到a,b的最大字段和 )
即： xm[o] = max( xm[o<<1], xm[o<<1|1], rm[o<<1]+lm[o<<1|1])
//注意这里是左子树和右子树的最大子段和，而不是lm[o] 和 rm[o], 因为它最大的时候可不经过边界
lm[o] = max(lm[o<<1], sumv[o<<1]+lm[o<<1|1] )
rm[o] = max(rm[o<<1|1], sumv[o<<1|1]+rm[o<<1] )

请思考后参考（第一次重构代码emm

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 500000+99

int n,m, a[MAX];


struct node{
	int sum, lm, rm, xm;
}tr[MAX<<2];

void push_up(int o) {
    tr[o].sum = tr[o<<1].sum + tr[o<<1|1].sum ;
    tr[o].lm = max(tr[o<<1].lm , tr[o<<1].sum + tr[o<<1|1].lm );
    tr[o].rm = max(tr[o<<1|1].rm , tr[o<<1|1].sum + tr[o<<1].rm );
    tr[o].xm = max( max(tr[o<<1].xm , tr[o<<1|1].xm ) , tr[o<<1].rm+tr[o<<1|1].lm );
    return ;
}

void build(int o, int l, int r) {
    if(l == r) {
	    tr[o].sum = tr[o].lm = tr[o].rm = tr[o].xm = a[l];
	    return ;
    }
    int mid = (l+r)>>1;
    build(o<<1, l, mid);
    build(o<<1|1, mid+1, r);
    push_up(o);
}

void update(int o, int l, int r, int t, int v) {
    if(l == r) {
        tr[o].sum = tr[o].lm = tr[o].rm = tr[o].xm  = v;
        return ;
    }
    int mid = (l+r)>>1;
    if(t <= mid) update(o<<1, l, mid, t, v);
    else update(o<<1|1, mid+1, r, t, v);
    push_up(o);
}

node query(int o, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return tr[o];
    node rson, lson;
    int f1 = 0, f2 = 0;
    int mid = (l+r)>>1;
    if(ql <= mid) lson = query(o<<1, l, mid, ql, qr), f1 = 1;
    if(mid < qr) rson = query(o<<1|1, mid+1, r, ql, qr), f2 = 1;
    if(f1 == 0) return rson;
    else if(f2 == 0) return lson;
    else {//如果区间同时包含中线左右边则需进行update时一样的操作。
    	node tmp;
    	tmp.sum = lson.sum + rson.sum ;
    	tmp.lm = max(lson.lm , lson.sum + rson.lm );
    	tmp.rm = max(rson.rm , rson.sum + lson.rm );
    	tmp.xm = max( max(lson.xm , rson.xm ), lson.rm + rson.lm );
    	return tmp;
	}
    
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    build(1, 1, n);
    int x,y,tmp;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d",&tmp, &x, &y);
        if(tmp == 1) { if(x > y) swap(x,y); printf("%d
", query(1, 1, n, x, y).xm  );}
        else update(1, 1, n, x, y);
    }
    return 0;
}

双倍经验福利： [Usaco2008 Feb]Hotel 旅馆