萌新64分求助

芝士记录

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
using namespace std;

#define maxn 500000
#define ll long long
#define ls(x) (x<<1)
#define rs(x) ((x<<1) | 1)

inline ll read();

struct node{
    ll s,sl,sr,sum;
};
ll n,m;
ll base[maxn];
node t[(maxn<<2)+10];

void push_up(ll rt){
    node la=t[ls(rt)],ra=t[rs(rt)];
    t[rt].sum=la.sum+ra.sum;
    t[rt].sl=max(la.sl,la.sum+ra.sl);
    t[rt].sr=max(ra.sr,ra.sum+la.sr);
    t[rt].s=max(max(la.s,ra.s),la.sr+ra.sl);
}

void build(ll rt,ll l,ll r){
    ll mid=(l+r) >> 1;
    if(l==r){
        t[rt].sl=base[l];t[rt].sr=base[l];t[rt].s=base[l],t[rt].sum=base[l];
        return;
    }
    build(ls(rt),l,mid);
    build(rs(rt),mid+1,r);
    push_up(rt);
    //cout<<l<<" " << r<<": "<<t[rt].s<<endl;
}

void change(ll rt,ll l,ll r,ll p,ll v){
    if(l==r){
        t[rt].sl=v;t[rt].sr=v;t[rt].s=v;t[rt].sum=v;
        return;
    }
    ll mid=(l+r)>>1;
    if(p<=mid){
        change(ls(rt),l,mid,p,v);
    }
    else{
        change(rs(rt),mid+1,r,p,v);
    }
    push_up(rt);
}

node query(ll rt,ll l,ll r,ll ql,ll qr){
    if(ql<=l && r<=qr){
        return t[rt];
    }
    ll mid=(l+r)>>1;
    if(mid>=qr){
        return query(ls(rt),l,mid,ql,qr);
    }
    if(mid<ql){
        return query(rs(rt),mid+1,r,ql,qr);
    }
    node res,a,b;
    a=query(ls(rt),l,mid,ql,qr);
    b=query(rs(rt),mid+1,r,ql,qr);
    res.sl=max(a.sl,a.sum+b.sl);
    res.sr=max(b.sr,b.sum+a.sr);
    res.s=max(max(a.s,b.s),a.sr+b.sl);
    res.sum=a.sum+b.sum;
    return res;
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)   base[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;i++){
        ll type=read();
        if(type==1){
            ll a=read(),b=read();
            node ans=query(1,1,n,min(a,b),max(a,b));
            printf("%lld\n",ans.s);
        }
        if(type==2){
            ll p=read(),v=read();
            change(1,1,n,p,v);
        }
    }
    return 0;
}
ll read(){ll w=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}