9分求助,qwq

P4513 小白逛公园

_Xiuer @ 2020-10-15 09:46:51


#include<iostream>
#include<cstdio>
#define N 500010
using namespace std;
int n,m,q[N],tot;
struct Segment_Tree{
    int l,r,sum;
    int Pre_sum;  //---最大前缀和 
    int Last_sum;  //--最大后缀和 
    int Part_sum;  //--最大子段和 
} s[N*4],w[N],ans;
void re(int &x)
{
    int t=0;x=0;char i=getchar();
    if(i=='-') t=1;
    while(i<'0'||i>'9') i=getchar();
    while(i>='0'&&i<='9') x=(x<<1)+(x<<3)+i-'0',i=getchar();
    if(t) x=-x;
}
void build(int p,int l,int r)
{
    s[p].l=l;s[p].r=r;
    if(l==r)
    {
        s[p].sum=q[l];s[p].Pre_sum=q[l];
        s[p].Last_sum=q[l];s[p].Part_sum=q[l];
        return;
    }
    int mid=(l+r)/2;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    s[p].sum=s[p<<1].sum+s[p<<1|1].sum;
    s[p].Pre_sum=max(s[p<<1].Pre_sum,s[p<<1].sum+s[p<<1|1].Pre_sum);
    s[p].Last_sum=max(s[p<<1|1].Last_sum,s[p<<1|1].sum+s[p<<1].Last_sum);
    s[p].Part_sum=max(s[p<<1].Part_sum,max(s[p<<1|1].Part_sum,s[p<<1].Last_sum+s[p<<1|1].Pre_sum));
}
void update(int p,int l,int r,int d)
{
    if(l<=s[p].l&&r>=s[p].r)
    {
        s[p].sum=d;s[p].Pre_sum=d;
        s[p].Last_sum=d;s[p].Part_sum=d;
        return;
    }
    int mid=(s[p].l+s[p].r)/2;
    if(l<=mid) update(p<<1,l,r,d);
    if(r>mid) update(p<<1|1,l,r,d);
    s[p].sum=s[p<<1].sum+s[p<<1|1].sum;
    s[p].Pre_sum=max(s[p<<1].Pre_sum,s[p<<1].sum+s[p<<1|1].Pre_sum);
    s[p].Last_sum=max(s[p<<1|1].Last_sum,s[p<<1|1].sum+s[p<<1].Last_sum);
    s[p].Part_sum=max(s[p<<1].Part_sum,max(s[p<<1|1].Part_sum,s[p<<1].Last_sum+s[p<<1|1].Pre_sum));
}
void query(int p,int l,int r)
{
    if(l<=s[p].l&&r>=s[p].r) {w[++tot]=s[p];return;}
    int mid=(s[p].l+s[p].r)/2;
    if(l<=mid) query(p<<1,l,r);
    if(r>mid) query(p<<1|1,l,r);
}
void solve(Segment_Tree a,Segment_Tree b)
{
    if(a.l>=b.r) swap(a,b);
    ans.l=a.l;ans.r=b.r;
    ans.sum=a.sum+b.sum;
    ans.Pre_sum=max(a.Pre_sum,a.sum+b.Pre_sum);
    ans.Last_sum=max(a.Last_sum+b.sum,b.Last_sum);
    ans.Part_sum=max(a.Part_sum,max(b.Part_sum,a.Last_sum+b.Pre_sum));
}
int main()
{
    freopen("bai.in","r",stdin);
    freopen("bai.out","w",stdout);
    re(n);re(m);
    for(int i=1;i<=n;i++) re(q[i]);
    build(1,1,n);
    int op,x,y;
    for(int i=1;i<=m;i++)
    {
        re(op);re(x);re(y);
        if(op==1)
        {
            if(x>y) swap(x,y);
            tot=0;
            query(1,x,y);ans=w[1];
            for(int i=2;i<=tot;i++) solve(w[i],ans);
            printf("%d\n",ans.Part_sum);
        }
        else update(1,x,x,y);
    }
    return 0;
}

by _Xiuer @ 2020-10-15 10:01:42

好吧,死在了快读上


|