C26 线段树 区间最大子段和 C26 线段树 区间最大子段和

#include<bits/stdc++.h>
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
const int N=5e5+10, inf=0x3f;
struct trnode{ int l, r, ls, rs, s, ms;}tr[4*N];int a[N];
void merge(trnode &t, trnode l, trnode r)
{
    t.s=l.s+r.s;
    t.ls=max(l.ls, l.s+r.ls);
    t.rs=max(r.rs, r.s+l.rs);
    t.ms=max(l.rs+r.ls, max(l.ms, r.ms));
}
void bt(int p, int l, int r)
{
	tr[p]={l, r, 0, 0, 0, 0};
	if(l==r){tr[p].ls=tr[p].rs=tr[p].s=tr[p].ms=a[l];return ;}
	int m=(l+r)>>1;
	bt(lc(p), l, m);bt(rc(p), m+1, r);
	merge(tr[p], tr[lc(p)], tr[rc(p)]);
}
void change(int p, int x, int k)
{
	if(x<tr[p].l || tr[p].r<x) return ;
    if(tr[p].l==tr[p].r){tr[p].ls=tr[p].rs=tr[p].s=tr[p].ms=k;return;}
    change(lc(p), x, k);change(rc(p), x, k);
    merge(tr[p], tr[lc(p)], tr[rc(p)]);
}
trnode query(int p, int l, int r)
{
    if(l<=tr[p].l&&tr[p].r<=r)return tr[p];
    int mid=(tr[p].l+tr[p].r)/2;
    if(r<=mid)return query(lc(p), l, r);
    else if(l>=mid+1)return query(rc(p), l, r);
    else
	{
		trnode t;merge(t, query(lc(p), l, r), query(rc(p), l, r));
		return t;
	}
}
int main()
{
    int n, m;scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++)scanf("%d", &a[i]);
    bt(1, 1, n);
    for(int i=1;i<=m;i++)
    {
        int op, x, y;scanf("%d%d%d", &op, &x, &y);
        if(op==2)change(1, x, y);
        else {if(x>y)swap(x, y);printf("%d\n", query(1, x, y).ms);}
    }
    return 0;
}