如题

#include <iostream>
using namespace std;
int n,q,a[500010];
struct dot{
    int l,r;
    int sum,lmax,rmax;
	int dat;
};
dot t[500010*4];
void build(int p, int l, int r){
    t[p].l=l, t[p].r=r;
    if(l==r){
        t[p].sum=a[l];
		t[p].lmax=a[l];
		t[p].rmax=a[l]; 
		t[p].dat=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
	build(p*2+1,mid+1,r);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
    t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
    t[p].dat=max(t[p*2].dat,max(t[p*2+1].dat,t[p*2].rmax+t[p*2+1].lmax));
}

int Lmax(int p, int R){
    int l=t[p].l;
	int r=t[p].r;
	int mid=(l+r)/2;
    if(R==r) return t[p].lmax;
    if(R<=mid) return Lmax(p*2,R);
    return max(t[p*2].sum+Lmax(p*2+1,R), Lmax(p*2,mid));
}

int Rmax(int p, int L){
    int l=t[p].l;
	int r=t[p].r;
	int mid=(l+r)/2;
    if(L==l) return t[p].rmax;
    if(mid+1<=L) return Rmax(p*2+1,L);
    return max(t[p*2+1].sum+Rmax(p*2,L), Rmax(p*2+1,mid+1));
}

int getmax(int p,int L,int R){
    int l=t[p].l;
	int r=t[p].r;
	int mid=(l+r)/2;
    if(L==l&&R==r) return t[p].dat;
    if(l<=L&&R<=mid) return getmax(p*2,L,R);
    if(mid+1<=L&&R<=r) return getmax(p*2+1,L,R);
    return max(Rmax(p*2, L)+Lmax(p*2+1, R),max(getmax(p*2,L,mid),getmax(p*2+1,mid+1,R)));
}

void add(int p,int x,int k){
    int l=t[p].l;
	int r=t[p].r;
	int mid=(l+r)/2;
    if(l==r)
    {
        t[p].sum=k;
		t[p].lmax=k;
		t[p].rmax=k;
		t[p].dat=k;
        return;
    }
    if(x<=mid)
	    add(p*2,x,k);
    else add(p*2+1,x,k);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
    t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
    t[p].dat=max(t[p*2].dat,max(t[p*2+1].dat,t[p*2].rmax+t[p*2+1].lmax));
}

int main(){
	cin>>n;
    for(int i=1; i<=n; i++)
    	cin>>a[i];
    build(1, 1, n);
    cin>>q;
    while(q--){
        int op, x, y;
        cin>>op>>x>>y;
        if(k==1) cout<<getmax(1,x,y);
        else add(1,x,y);
    }
}