题解 SP1716 【GSS3 - Can you answer these queries III】

Ajwallet · 2018-08-21 20:42:05 · 题解

看到dalao们的题解都用了结构体，身为蒟蒻的我瑟瑟发抖，就打了个用两个变量来回答询问的，望管理给过

具体思路

维护我就不说了，完全跟dalao们的一样，但是在询问部分，如何不用结构体达到统计答案的目的呢？可以用两个变量ans和pre，一个表示最终答案，一个表示之前答案，就可以模拟结构体达到求解的目的了，这种方法的优势就是。。。 看起来爽

代码

#include<cstdio>
#include<algorithm>
#define ri register int
#define lson k<<1
#define rson k<<1|1
using namespace std;int sum[200001],lmax[200001],rmax[200001],n;
int dat[200001],a[50001],m,x,y,z,ans,pre;
inline void wh(ri k)//维护,Wei Hu
{
    sum[k]=sum[lson]+sum[rson];
    lmax[k]=max(lmax[lson],sum[lson]+lmax[rson]);
    rmax[k]=max(rmax[rson],sum[rson]+rmax[lson]);
    dat[k]=max(max(dat[lson],dat[rson]),rmax[lson]+lmax[rson]);
    return;
}
inline void build(ri k,ri l,ri r)//建树
{
    if(l==r)
    {
        sum[k]=a[l];lmax[k]=a[l];rmax[k]=a[l];dat[k]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);build(rson,mid+1,r);
    wh(k);
    return;
}
inline void change(ri k,ri l,ri r,ri x,ri d)//我这里没有多开两个数组而是多开了两个参数，因为听说这样比较快。。。
{
    if(l==r)
    {
        if(l==x){sum[k]=d;lmax[k]=d;rmax[k]=d;dat[k]=d;}//达到要修改的点则修改
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) change(lson,l,mid,x,d);else change(rson,mid+1,r,x,d);//修改
    wh(k);//维护
    return;
}
inline void ask(ri k,ri l,ri r,ri ql,ri qr)//询问
{
    if(ql<=l&&qr>=r)
    {
        ans=max(ans,dat[k]);//计算
        ans=max(ans,pre+lmax[k]);
        pre=max(rmax[k],pre+sum[k]);//维护pre
        return;
    }
    int mid=(l+r)>>1;
    int ans=0;
    if(ql<=mid) ask(lson,l,mid,ql,qr);
    if(qr>mid) ask(rson,mid+1,r,ql,qr);//继续向下
}
signed main()
{
    scanf("%d",&n);
    for(ri i=1;i<=n;i++) scanf("%d",a+i);
    build(1,1,n);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(x==1){ans=-1147483645;pre=-1147483645;ask(1,1,n,y,z);printf("%d\n",ans);}//注意这里的ans和pre不能开太小，要不然出现负数的时候可能会WA
        else change(1,1,n,y,z);//修改
    }
}