ac第一个点,9分求助!!!

P4513 小白逛公园

Dio_The_World @ 2023-11-05 20:02:08

#include <bits/stdc++.h>
#define For(i,s,e) for(int i=s;i<=e;i++)
#define dFor(i,s,e) for(int i=s;i>=e;i--)
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;
const int MaxN=1145141;
int n,q,a[MaxN],ans[4][MaxN<<2];
void push_up(int p){//0->l 1->r
    ans[2][p]=ans[2][ls]+ans[2][rs];
    ans[0][p]=max(ans[0][ls],ans[2][ls]+ans[0][rs]);
    ans[1][p]=max(ans[1][rs],ans[2][rs]+ans[1][ls]);
    ans[3][p]=max(max(ans[3][ls],ans[3][rs]),ans[1][ls]+ans[0][rs]);
}
void build(int p,int l,int r){
    if(l==r){
        ans[0][p]=ans[1][p]=ans[2][p]=ans[3][p]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(p);
}
void update(int n,int p,int k,int l,int r){
    if(n==l && n==r){
        ans[0][p]=ans[1][p]=ans[2][p]=ans[3][p]=k;
        return;
    }
    int mid=(l+r)>>1;
    if(n<=mid)update(n,ls,k,l,mid);
    if(n>mid)update(n,rs,k,mid+1,r);
    push_up(p);
}
int query(int nl,int nr,int l,int r,int p){
    if(nl<=l && r<=nr)
        return ans[3][p];
    int res=-LLONG_MAX;
    int mid=(l+r)>>1;
    if(nl<=mid)res=max(res,query(nl,nr,l,mid,ls));
    if(nr>mid)res=max(res,query(nl,nr,mid+1,r,rs));
    return res;
}
signed main(){
    scanf("%lld%lld",&n,&q);
    For(i,1,n)scanf("%lld",a+i);
    build(1,1,n);
    while(q--){
        int op,a,b;
        scanf("%lld%lld%lld",&op,&a,&b);
        if(op==2){
            update(a,1,b,1,n);
        }else if(op==1){
            if(b<a)swap(a,b);
            printf("%lld\n",query(a,b,1,n,1));
        }else{// \/调试代码不用看
            For(o,0,3){
            int i=1,j=1,e=1;
            while(1){
                if(e>(n<<1))break;
                for(j=1;j<=1<<(i-1);j++){cout<<ans[o][e++]<<" ";}
                cout<<endl;
                i++;
            }}
        }
    }
    return 0;
}
/*
5 114
1
2
-3
4
5
*/

by UYHW @ 2023-11-05 20:07:03

query合并左右区间


by Dio_The_World @ 2023-11-05 20:34:43

@UYHW 是这样吗,还是不行

#include <bits/stdc++.h>
#define For(i,s,e) for(int i=s;i<=e;i++)
#define dFor(i,s,e) for(int i=s;i>=e;i--)
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;
struct node{
    int l,r,m,s;
};
const int MaxN=1145141;
int n,q,a[MaxN],ans[4][MaxN<<2];
void push_up(int p){//0->l 1->r
    ans[2][p]=ans[2][ls]+ans[2][rs];
    ans[0][p]=max(ans[0][ls],ans[2][ls]+ans[0][rs]);
    ans[1][p]=max(ans[1][rs],ans[2][rs]+ans[1][ls]);
    ans[3][p]=max(max(ans[3][ls],ans[3][rs]),ans[1][ls]+ans[0][rs]);
}
void build(int p,int l,int r){
    if(l==r){
        ans[0][p]=ans[1][p]=ans[2][p]=ans[3][p]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(p);
}
void update(int n,int p,int k,int l,int r){
    if(n==l && n==r){
        ans[0][p]=ans[1][p]=ans[2][p]=ans[3][p]=k;
        return;
    }
    int mid=(l+r)>>1;
    if(n<=mid)update(n,ls,k,l,mid);
    if(n>mid)update(n,rs,k,mid+1,r);
    push_up(p);
}
node query(int nl,int nr,int l,int r,int p){
    if(nl<=l && r<=nr)
        return (node){ans[0][p],ans[1][p],ans[3][p],ans[2][p]};
    node res;
    int mid=(l+r)>>1;
    if(nl<=mid)res=query(nl,nr,l,mid,ls);
    else if(nr>mid)res=query(nl,nr,mid+1,r,rs);
    else if(nl<=mid && nr>mid){
        node x=query(nl,nr,l,mid,ls),y=query(nl,nr,mid+1,r,rs);
        res.l=max(x.l,x.s+y.l);
        res.r=max(y.r,y.s+x.r);
        res.m=max(max(x.m,y.m),x.r+y.l);
        res.s=x.s+y.s;
        return res;
    }
    return res;
}
signed main(){
    scanf("%lld%lld",&n,&q);
    For(i,1,n)scanf("%lld",a+i);
    build(1,1,n);
    while(q--){
        int op,a,b;
        scanf("%lld%lld%lld",&op,&a,&b);
        if(op==2){
            update(a,1,b,1,n);
        }else if(op==1){
            if(b<a)swap(a,b);
            printf("%lld\n",query(a,b,1,n,1).m);
        }else{
            For(o,0,3){
            int i=1,j=1,e=1;
            while(1){
                if(e>(n<<1))break;
                for(j=1;j<=1<<(i-1);j++){cout<<ans[o][e++]<<" ";}
                cout<<endl;
                i++;
            }}
        }
    }
    return 0;
}
/*
5 114
1
2
-3
4
5
*/

by Dio_The_World @ 2023-11-05 20:38:30

@UYHW 过了过了,谢谢巨佬


by Dio_The_World @ 2023-11-05 20:39:36

@Dio_The_World 已经过了,顺序不对,应该先判断nl<=mid && nr>mid再判断后面两个


|