蒟蒻刚学OI，求助线段树

小恐 @ 2020-05-25 09:22:54

#include<stdio.h>
#include<algorithm>
using namespace std;
const int NR=5e5+5;
const int MR=1e5+5;
const int INF=0x3f3f3f3f;
typedef long long LL;
int read()
{
    int x=0;
    int bei=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            bei=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*=bei;
}
int a[NR];
struct Segtree
{
    int sum,qian,hou,zong;
}segtree[NR<<2];
void build(int x,int l,int r)
{
    if(l==r)
    {
        segtree[x]=(Segtree){a[l],a[l],a[l],a[l]};
        return;
    }
    int ls=x<<1,rs=x<<1|1;
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    segtree[x].sum=segtree[ls].sum+segtree[rs].sum;
    segtree[x].zong=max(segtree[ls].hou+segtree[rs].qian,max(segtree[ls].zong,segtree[rs].zong));
    segtree[x].qian=max(segtree[ls].sum+segtree[rs].qian,segtree[ls].qian);
    segtree[x].hou=max(segtree[rs].sum+segtree[ls].hou,segtree[rs].hou);
}
int lst;
int ans;
void query(int x,int l,int r,int nl,int nr)
{
    if(nl<=l&&r<=nr)
    {
        ans=max(ans,max(lst+segtree[x].qian,segtree[x].zong));
        lst=segtree[x].hou;
        return;
    }
    int mid=l+r>>1;
    int ls=x<<1,rs=x<<1|1;
    if(nl<=mid)
        query(ls,l,mid,nl,nr);
    if(nr>mid)
        query(rs,mid+1,r,nl,nr);
}
void modify(int x,int l,int r,int nx,int k)
{
    if(l==r)
    {
        segtree[x]=(Segtree){k,k,k,k};
        return;
    }
    int ls=x<<1,rs=x<<1|1;
    int mid=l+r>>1;
    if(nx<=mid)
        modify(ls,l,mid,nx,k);
    else
        modify(rs,mid+1,r,nx,k);
    segtree[x].sum=segtree[ls].sum+segtree[rs].sum;
    segtree[x].zong=max(segtree[ls].hou+segtree[rs].qian,max(segtree[ls].zong,segtree[rs].zong));
    segtree[x].qian=max(segtree[ls].sum+segtree[rs].qian,segtree[ls].qian);
    segtree[x].hou=max(segtree[rs].sum+segtree[ls].hou,segtree[rs].hou);
}
int main()
{
    //freopen("P4513.in","r",stdin);
    //freopen("P4513.out","w",stdout);
    int n=read(),m=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    build(1,1,n);
    while(m--)
    {
        int p=read();
        if(p==1)
        {
            int l=read(),r=read();
            lst=ans=-INF;
            query(1,1,n,min(l,r),max(l,r));
            printf("%d\n",ans);
        }
        else
        {
            int x=read(),s=read();
            modify(1,1,n,x,s);
        }
    }
    return 0;
}

by 水分子 @ 2020-05-25 09:42:05

qndmx

by Miller2019 @ 2020-05-25 09:57:32

stoorz

by 小恐 @ 2020-05-25 09:57:49

没人理我这个菜鸡qwq

by Werner_Yin @ 2020-05-25 10:25:30

orz

by Werner_Yin @ 2020-05-25 10:26:32

by 小恐 @ 2020-05-25 10:55:48

@Werner_Yin 对啊

by Werner_Yin @ 2020-05-25 11:29:14

@小恐 我没这么写过query，我当初是直接让query返回类型为Segtree

by Werner_Yin @ 2020-05-25 11:46:29

@小恐 感觉这么写会发生玄学错误，如果改一下就没问题了。

#include<stdio.h>
#include<algorithm>
using namespace std;
const int NR=5e5+5;
const int MR=1e5+5;
const int INF=0x3f3f3f3f;
typedef long long LL;
int read()
{
    int x=0;
    int bei=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            bei=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*bei;
}
int a[NR];
struct Segtree
{
    long long sum,qian,hou,zong;
    Segtree operator +(const Segtree &b)const{
        Segtree c;
        c.sum=sum+b.sum;
        c.zong=max(hou+b.qian,max(zong,b.zong));
        c.qian=max(sum+b.qian,qian);
        c.hou=max(b.sum+hou,b.hou);
        return c;
    }
}segtree[NR<<2];
void build(int x,int l,int r)
{
    if(l==r)
    {
        segtree[x]=(Segtree){a[l],a[l],a[l],a[l]};
        return;
    }
    int ls=x<<1,rs=x<<1|1;
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    segtree[x].sum=segtree[ls].sum+segtree[rs].sum;
    segtree[x].zong=max(segtree[ls].hou+segtree[rs].qian,max(segtree[ls].zong,segtree[rs].zong));
    segtree[x].qian=max(segtree[ls].sum+segtree[rs].qian,segtree[ls].qian);
    segtree[x].hou=max(segtree[rs].sum+segtree[ls].hou,segtree[rs].hou);

}
int lst;
int ans;
Segtree query(int x,int l,int r,int nl,int nr)
{
    if(nl<=l&&r<=nr)
    {
        return segtree[x];
    }
    int mid=(l+r)>>1;
    int ls=x<<1,rs=x<<1|1;
    if(nr<=mid)return query(ls,l,mid,nl,nr) ;
    if(nl>mid)return query(rs,mid+1,r,nl,nr);
    return query(ls,l,mid,nl,nr) + query(rs,mid+1,r,nl,nr);
}
void modify(int x,int l,int r,int nx,int k)
{
    if(l==r)
    {
        if(nx==l)segtree[x]=(Segtree){k,k,k,k};
        return;
    }
    int ls=x<<1,rs=x<<1|1;
    int mid=(l+r)>>1;
    if(nx<=mid)
        modify(ls,l,mid,nx,k);
    if(nx>mid)
        modify(rs,mid+1,r,nx,k);
    segtree[x].sum=segtree[ls].sum+segtree[rs].sum;
    segtree[x].zong=max(segtree[ls].hou+segtree[rs].qian,max(segtree[ls].zong,segtree[rs].zong));
    segtree[x].qian=max(segtree[ls].sum+segtree[rs].qian,segtree[ls].qian);
    segtree[x].hou=max(segtree[rs].sum+segtree[ls].hou,segtree[rs].hou);
}
int main()
{
    //freopen("P4513.in","r",stdin);
    //freopen("P4513.out","w",stdout);
    int n=read(),m=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    build(1,1,n);
    while(m--)
    {
        int p=read();
        if(p==1)
        {
            int l=read(),r=read();
            printf("%lld\n",query(1,1,n,min(l,r),max(l,r)).zong);
        }
        else
        {
            int x=read(),s=read();
            modify(1,1,n,x,s);
        }
    }
    return 0;
}

by Werner_Yin @ 2020-05-25 11:56:26

@小恐 如图![]( 假设橙色区间为求值区间，而{1+2+3} 区间为最佳答案，但是这样只会考虑到2+3 区间，不会考虑最佳方案

by Werner_Yin @ 2020-05-25 11:59:39

@小恐 我又想到了新的方法，你只要把源代码query的

lst=segtree[x].hou;

改为

lst=max(lst+segtree[x].sum,segtree[x].hou);

就可以了