求助 关于维护线段树的区间

回复帖子

@新手之帆  2021-02-19 13:53 回复

RT 谢谢!

我90pts的代码 是维护线段的 而我在其他扫描线的题都是这种打法且都能过

也就是

// 维护mx值  即扫描线能覆盖到的最大值 

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>

#define N (int)(1e5+5)
#define ls (cur<<1)
#define rs (ls|1)
#define int long long

using namespace std; 

int ny[N];
int n,w,h;

struct node {
    int h,l,r,fl;
}g[N];

struct tr {
    int sum,tag;
}t[N];

int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

void push_up(int cur) {
    t[cur].sum=max(t[ls].sum,t[rs].sum);
}

void push_down(int cur) {
    if(!t[cur].tag) return;
    t[ls].sum+=t[cur].tag; t[rs].sum+=t[cur].tag;
    t[ls].tag+=t[cur].tag; t[rs].tag+=t[cur].tag;
    t[cur].tag=0;
}

void update(int cur,int l,int r,int cl,int cr,int x) {
    if(ny[l]>=cr||ny[r]<=cl) return;
    if(cl<=ny[l]&&ny[r]<=cr) {
        t[cur].sum+=x;
        t[cur].tag+=x;
        return;
    }
    int mid=(l+r)>>1;
    push_down(cur);
    update(ls,l,mid,cl,cr,x);
    update(rs,mid,r,cl,cr,x);
    push_up(cur);
}

bool cmp(node x,node y) {
    return x.h==y.h?x.fl>y.fl:x.h<y.h;
}

signed main() {
    int tt=rd();
    while(tt--) {
        memset(g,0,sizeof(g));
        memset(ny,0,sizeof(ny));
        memset(t,0,sizeof(t));
        n=rd(); w=rd(); h=rd();
        int x,y,z;
        for(int i=1;i<=n;i++) {
            x=rd(); y=rd(); z=rd();
            g[(i<<1)-1]=node{x,y,y+h-1,z};
            g[i<<1]=node{x+w-1,y,y+h-1,-z};
            ny[(i<<1)-1]=y; ny[i<<1]=y+h-1;
        }
        n<<=1;
        sort(g+1,g+1+n,cmp);
        sort(ny+1,ny+1+n);
        int ans=0,tot=0;
        for(int i=1;i<=n;i++) if(ny[i]!=ny[i+1]) ny[++tot]=ny[i];
        for(int i=1;i<n;i++) {
            update(1,1,tot,g[i].l,g[i].r,g[i].fl);
            ans=max(ans,t[1].sum);
        }
        printf("%lld\n",ans);
    }   
}

但是在这道题 就似乎要维护2条线段之间 改成这样就过了 区别在update函数和调用update函数

// 维护mx值  即扫描线能覆盖到的最大值 

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>

#define N (int)(1e6+5)
#define ls (cur<<1)
#define rs (ls|1)
#define int long long

using namespace std; 

int ny[N];
int n,w,h;

struct node {
    int h,l,r,fl;
}g[N];

struct tr {
    int sum,tag;
}t[N];

int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

void push_up(int cur) {
    t[cur].sum=max(t[ls].sum,t[rs].sum);
}

void push_down(int cur) {
    if(!t[cur].tag) return;
    t[ls].sum+=t[cur].tag; t[rs].sum+=t[cur].tag;
    t[ls].tag+=t[cur].tag; t[rs].tag+=t[cur].tag;
    t[cur].tag=0;
}

void update(int cur,int l,int r,int cl,int cr,int x) {
    if(ny[l]>cr||ny[r]<cl) return;
    if(cl<=ny[l]&&ny[r]<=cr) {
        t[cur].sum+=x;
        t[cur].tag+=x;
        return;
    }
    int mid=(l+r)>>1;
    push_down(cur);
    update(ls,l,mid,cl,cr,x);
    update(rs,mid+1,r,cl,cr,x);
    push_up(cur);
}

bool cmp(node x,node y) {
    return x.h==y.h?x.fl>y.fl:x.h<y.h;
}

signed main() {
    int tt=rd();
    while(tt--) {
        memset(g,0,sizeof(g));
        memset(ny,0,sizeof(ny));
        memset(t,0,sizeof(t));
        n=rd(); w=rd(); h=rd();
        int x,y,z;
        for(int i=1;i<=n;i++) {
            x=rd(); y=rd(); z=rd();
            g[(i<<1)-1]=node{x,y,y+h-1,z};
            g[i<<1]=node{x+w-1,y,y+h-1,-z};
            ny[(i<<1)-1]=y; ny[i<<1]=y+h-1;
        }
        n<<=1;
        sort(g+1,g+1+n,cmp);
        sort(ny+1,ny+1+n);
        int ans=0,tot=0;
        for(int i=1;i<=n;i++) if(ny[i]!=ny[i+1]) ny[++tot]=ny[i];
        for(int i=1;i<=n;i++) {
            update(1,1,tot-1,g[i].l,g[i].r,g[i].fl);
            ans=max(ans,t[1].sum);
        }
        printf("%lld\n",ans);
    }   
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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