~~萌新求助系列~~ 求助,一直9分 qwq

P4513 小白逛公园

顾z @ 2018-09-27 10:06:54

#include<bits/stdc++.h>
#define IL inline
#define RI register int
#define N 500008
#define ls o<<1
#define rs o<<1|1
using namespace std;
IL void in(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();}
    while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int tr[N<<3],ssum[N<<3],lsum[N<<3],rsum[N<<3],n,m;
IL void up(int o)
{
    tr[o]=tr[ls]+tr[rs];
    ssum[o]=max(max(ssum[ls],ssum[rs]),rsum[ls]+lsum[rs]);
    lsum[o]=max(lsum[ls],tr[ls]+lsum[rs]);
    rsum[o]=max(rsum[rs],tr[rs]+rsum[ls]);
}
void build(int o,int l,int r)
{
    if(l==r)
    {
        in(tr[o]);
        ssum[o]=lsum[o]=rsum[o]=tr[o];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    up(o);
}
int query(int o,int l,int r,int x,int y)
{
    if(x<=l and y>=r)return ssum[o];
    int mid=(l+r)>>1;
    int ret=-214748364;
    if(x<=mid)ret=max(query(ls,l,mid,x,y),ret);
    if(y>mid)ret=max(query(rs,mid+1,r,x,y),ret);
    return ret;
}
void change(int o,int l,int r,int pos,int del)
{
    if(l==r){ssum[o]=lsum[o]=rsum[o]=tr[o]=del;return;}
    int mid=(l+r)>>1;
    if(pos<=mid)
        change(ls,l,mid,pos,del);
    else 
        change(rs,mid+1,r,pos,del);
    up(o);
}
int main()
{
    in(n),in(m);
    build(1,1,n);
    for(RI opt;m;m--)
    {
        in(opt);
        if(opt==1)
        {
            RI l,r;
            in(l),in(r);
            if(l>r)swap(l,r);
            printf("%d\n",query(1,1,n,l,r));
        }
        if(opt==2)
        {
            RI pos,del;
            in(pos),in(del);
            change(1,1,n,pos,del);
        }
    }
}

by enceladus @ 2018-09-27 10:20:58

萌新真阔怕


by Dystractor @ 2018-09-27 10:21:21

求最大值那里写错了
很明显你需要分治啊,,,,


by 顾z @ 2018-09-27 10:29:09

@Dystractor dalao能具体讲讲嘛 qwq, 表示懵了 emm


by 顾z @ 2018-09-27 10:36:20

@Dystractor 不用麻烦大佬了 ,已经改过 qwq


|