萌新刚学oi1ms,线段树9pts求调

#include <iostream>
#include <cstdio>
#define ls (s << 1)
#define rs (s << 1 | 1)
using namespace std;
struct node{
    int l,r,len,sum,mxl,mxr,mxsum;
}T[5010110];
int n,t,A[501111];
void pushup(node& fa,const node les,const node ris)
{
    fa.mxsum = max(les.mxr + ris.mxl,max(les.mxsum,ris.mxsum));
    fa.mxl = max(les.mxl,les.sum + ris.mxl);
    fa.mxr = max(ris.mxl,ris.sum + les.mxr);
    fa.sum = les.sum + ris.sum;
}
void build(int s,int l,int r)
{
    T[s] = (node){l,r,r - l + 1,0,-10000000,-10000000,-1000000};
    if(l == r)
    {
        T[s].sum = T[s].mxl = T[s].mxr = T[s].mxsum = A[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls,l,mid);
    build(rs,mid + 1,r);
    pushup(T[s],T[ls],T[rs]);
}
void modify(int s,int p,int x)
{
    if(T[s].l == T[s].r && T[s].r == p)
    {
        T[s].mxl = T[s].mxr = T[s].mxsum = T[s].sum = x;
        return;
    }
    int mid = (T[s].l + T[s].r) >> 1;
    if(p > mid)modify(rs,p,x);
    else modify(ls,p,x);
    pushup(T[s],T[ls],T[rs]);
}
node query(int s,int l,int r)
{
    if(T[s].l == l && T[s].r == r)return T[s];
    int mid = (T[s].l + T[s].r) >> 1;
    node ans;
    if(l > mid)ans = query(rs,l,r);
    else if(r <= mid)ans = query(ls,l,r);
    else
    {
        pushup(T[s],query(ls,l,mid),query(rs,mid + 1,r));
        ans = T[s];
    }
    return ans;
}
int main()
{
    cin>>n>>t;
    int i,j;
    for(i = 1;i <= n;i++)cin>>A[i];
    build(1,1,n);
    while(t--)
    {
        int op;cin>>op;
        if(op == 1)
        {
            int l,r;cin>>l>>r;
            if(l > r)swap(l,r);
            cout<<query(1,l,r).mxsum<<endl;
        }
        else
        {
            int p,x;cin>>p>>x;
            modify(1,p,x);
        }
    }
    return 0;
}