样例过不了求助

P4513 小白逛公园

cx2021ghj @ 2024-10-23 07:58:37

#include<bits/stdc++.h>
using namespace std;
struct ghj{
    int l,r;
    long long ans,ansl,ansr,cnt;
}tree[2000009];
int n,m,a[500009],op,x,l,r,d;
void push_up(int q){
    tree[q].cnt=tree[q*2].cnt+tree[q*2+1].cnt;
    tree[q].ansl=max(tree[q*2].ansl,tree[q*2].cnt+tree[q*2+1].ansl);
    tree[q].ansr=max(tree[q*2+1].ansr,tree[q*2+1].cnt+tree[q*2].ansr);
    tree[q].ans=max(max(tree[q*2].ans,tree[q*2+1].ans),tree[q*2].ansr+tree[q*2+1].ansl);
}
void build(int l,int r,int p=1){
    tree[p].l=l;
    tree[p].r=r;
    if(l==r){
        cin>>tree[p].cnt;
        tree[p].ansl=tree[p].ansr=tree[p].ans=tree[p].cnt;
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    push_up(p);
}
void update(int x,int d,int p=1){
    if(tree[p].l==tree[p].r){
        tree[p].cnt=d;
        tree[p].ansl=d;
        tree[p].ansr=d;
        tree[p].ans=d;
        return;
    }
    int mid=(tree[p].l+tree[p].r)/2;
    if(x<=mid) update(x,d,p*2);
    else update(x,d,p*2+1);
    push_up(p);
}
ghj query(int p,int l,int r){
    if(l<=tree[p].l && tree[p].r<=r) return tree[p];
    int mid=(tree[p].l+tree[p].r)/2;
    if(r<=mid) return query(p*2,l,r);
    else{
        if(r>mid) return query(p*2+1,l,r);
        else{
            ghj t,a=query(p*2,l,r),b=query(p*2+1,l,r);
            t.ansl=max(a.ansl,a.cnt+b.ansl);
            t.ansr=max(b.ansr,a.ansr+b.cnt);
            t.ans=max(max(a.ans,b.ans),a.ansr+b.ansl);
            return t;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    build(1,n,1);
    while(m--){
        cin>>op;
        if(op==1){
            cin>>l>>r;
            if(l>r)swap(l,r);
            cout<<query(1,l,r).ans<<'\n';
        }
        else{
            cin>>x>>d;
            update(x,d);
        }
    }
}

by ShiYufan @ 2024-10-23 08:33:18

毋庸置疑线段树有问题


by HongLou_LaMiYa @ 2024-10-26 10:58:06

query写错了

#include<bits/stdc++.h>
using namespace std;
struct ghj{
    int l,r;
    long long ans,ansl,ansr,cnt;
}tree[2000009];
int n,m,a[500009],op,x,l,r,d;
void push_up(int q){
    tree[q].cnt=tree[q*2].cnt+tree[q*2+1].cnt;
    tree[q].ansl=max(tree[q*2].ansl,tree[q*2].cnt+tree[q*2+1].ansl);
    tree[q].ansr=max(tree[q*2+1].ansr,tree[q*2+1].cnt+tree[q*2].ansr);
    tree[q].ans=max(max(tree[q*2].ans,tree[q*2+1].ans),tree[q*2].ansr+tree[q*2+1].ansl);
}
void build(int l,int r,int p=1){
    tree[p].l=l;
    tree[p].r=r;
    if(l==r){
        cin>>tree[p].cnt;
        tree[p].ansl=tree[p].ansr=tree[p].ans=tree[p].cnt;
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    push_up(p);
}
void update(int x,int d,int p=1){
    if(tree[p].l==tree[p].r){
        tree[p].cnt=d;
        tree[p].ansl=d;
        tree[p].ansr=d;
        tree[p].ans=d;
        return;
    }
    int mid=(tree[p].l+tree[p].r)/2;
    if(x<=mid) update(x,d,p*2);
    else update(x,d,p*2+1);
    push_up(p);
}
ghj query(int p,int l,int r){
    if(l<=tree[p].l && tree[p].r<=r) return tree[p];
    int mid=(tree[p].l+tree[p].r)/2;
    if(r<=mid) return query(p*2,l,r);
    else{
        if(l>mid) return query(p*2+1,l,r);//这里
        else{
            ghj t,a=query(p*2,l,r),b=query(p*2+1,l,r);
            t.ansl=max(a.ansl,a.cnt+b.ansl);
            t.ansr=max(b.ansr,a.ansr+b.cnt);
            t.ans=max(max(a.ans,b.ans),a.ansr+b.ansl);
            return t;
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    build(1,n,1);
    while(m--){
        cin>>op;
        if(op==1){
            cin>>l>>r;
            if(l>r)swap(l,r);
            cout<<query(1,l,r).ans<<'\n';
        }
        else{
            cin>>x>>d;
            update(x,d);
        }
    }
}

给你交了一下,AC的


|