求助。关于线段树的区间

回复帖子

@春风  2020-09-24 22:04 回复

这是我原来的代码(未AC)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e4+10;
int n,T;
ll W,H,X[MAXN],ans;
struct Segt{
    int l,r;
    ll sum,jud;
}t[MAXN<<3];
struct Seg{
    ll l,r,h,w;
    bool operator < (const Seg &b)const{
        if(h==b.h) return w>b.w;
        return h<b.h;
    }
}line[MAXN<<1];
ll Max(ll x,ll y) { return x>y?x:y; }
void Build(int p,int l,int r){
    t[p].l=l; t[p].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    Build(p<<1,l,mid);
    Build(p<<1|1,mid+1,r);
}
void Pushdown(int p){
    t[p<<1].jud+=t[p].jud;
    t[p<<1|1].jud+=t[p].jud;
    t[p<<1].sum+=t[p].jud;
    t[p<<1|1].sum+=t[p].jud;
    t[p].jud=0;
}
void Leadin(int p,int pl,int pr,ll we){
    int l=t[p].l,r=t[p].r;
    // printf("%d %d %d %d\n",l,r,pl,pr);
    if(pl>=r+1||pr<=l) return;
    if(pl<=l&&pr>=r+1){
        t[p].jud+=we;
        t[p].sum+=we;
        return;
    }
    Pushdown(p);
    Leadin(p<<1,pl,pr,we);
    Leadin(p<<1|1,pl,pr,we);
    t[p].sum=Max(t[p<<1].sum,t[p<<1|1].sum);
}
signed main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%lld%lld",&n,&W,&H);
        ans=0;
        memset(t,0,sizeof t);
        for(int i=1;i<=n;++i){
            ll x,y,light;
            scanf("%lld%lld%lld",&x,&y,&light);
            line[2*i-1]=(Seg){x,x+W-1,y,light};
            line[2*i]=(Seg){x,x+W-1,y+H-1,-light};
            X[2*i-1]=x;
            X[2*i]=x+W-1;
        }
        n<<=1;
        sort(X+1,X+1+n);
        sort(line+1,line+1+n);
        int tot=unique(X+1,X+1+n)-X-1;
        Build(1,1,tot-1);
        // for(int i=1;i<=n;++i) printf("line[%d]=%lld %lld %lld %lld\n",i,line[i].l,line[i].r,line[i].h,line[i].w);
        for(int i=1;i<=n;++i){
            int pl=lower_bound(X+1,X+1+tot,line[i].l)-X;
            int pr=lower_bound(X+1,X+1+tot,line[i].r)-X;
            printf("line=%d %d %lld %lld\n",pl,pr,line[i].l,line[i].r);
            Leadin(1,pl,pr,line[i].w);
            printf("sum%d=%lld\n",i,t[1].sum);
            ans=Max(ans,t[1].sum);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

这是我的AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e4+10;
int n,T;
ll W,H,X[MAXN<<1],ans;
struct Segt{
    int l,r;
    ll sum,jud;
}t[MAXN<<3];
struct Seg{
    ll l,r,h,w;
    bool operator < (const Seg &b)const{
        if(h==b.h) return w>b.w;
        return h<b.h;
    }
}line[MAXN<<2];
ll Max(ll x,ll y) { return x>y?x:y; }
void Build(int p,int l,int r){
    t[p].l=l; t[p].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    Build(p<<1,l,mid);
    Build(p<<1|1,mid+1,r);
}
void Pushdown(int p){
    t[p<<1].jud+=t[p].jud;
    t[p<<1|1].jud+=t[p].jud;
    t[p<<1].sum+=t[p].jud;
    t[p<<1|1].sum+=t[p].jud;
    t[p].jud=0;
}
void Leadin(int p,int pl,int pr,ll we){
    int l=t[p].l,r=t[p].r;
    // printf("%d %d %d %d\n",l,r,pl,pr);
    // if(pl>r||pr<l) return;
    if(pl<=l&&pr>=r){
        t[p].jud+=we;
        t[p].sum+=we;
        return;
    }
    int mid=(l+r)>>1;
    Pushdown(p);
    if(pl<=mid) Leadin(p<<1,pl,pr,we);
    if(pr>mid) Leadin(p<<1|1,pl,pr,we);
    t[p].sum=Max(t[p<<1].sum,t[p<<1|1].sum);
}
signed main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%d%lld%lld",&n,&W,&H);
        ans=0;
        memset(t,0,sizeof t);
        memset(line,0,sizeof line);
        for(int i=1;i<=n;++i){
            ll x,y,light;
            scanf("%lld%lld%lld",&x,&y,&light);
            line[2*i-1]=(Seg){x,x+W-1,y,light};
            line[2*i]=(Seg){x,x+W-1,y+H-1,-light};
            X[2*i-1]=x;
            X[2*i]=x+W-1;
        }
        n<<=1;
        sort(X+1,X+1+n);
        sort(line+1,line+1+n);
        int tot=unique(X+1,X+1+n)-X-1;
        Build(1,1,tot-1);
        // for(int i=1;i<=n;++i) printf("line[%d]=%lld %lld %lld %lld\n",i,line[i].l,line[i].r,line[i].h,line[i].w);
        for(int i=1;i<n;++i){
            int pl=lower_bound(X+1,X+1+tot,line[i].l)-X-1;
            int pr=lower_bound(X+1,X+1+tot,line[i].r)-X-1;
            // printf("line=%d %d %lld %lld\n",pl,pr,line[i].l,line[i].r);
            Leadin(1,pl,pr,line[i].w);
            // printf("sum%d=%lld\n",i,t[1].sum);
            ans=Max(ans,t[1].sum);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

提问: 将Leadin函数中的r改成r+1且pr<=l,pl>=r+1的判断就不行,连样例都过不了(在扫描线的模板中这样做是没问题的,而且线段树区间的定义就是[l,r]代表[l,r+1]的区间)。 而必须以r为边界且要进行pl<=mid,pr>mid的判断才行,这是为什么?

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。