Luogu

POJ

分析

可以把星星往右上扩张,形成一个把窗户的右上角放在这个区域中就可以看到这个星星的矩形。

设星星坐标为$(x,y)$,则这个矩形的右上角为$(x+w-1,y+h-1)$。这样可以保证边界不算。

然后就可以用扫描线做。需要支持区间修改和区间最大值。

每条扫描线就是$(x,y,y+h-1,l)$和$(x+w,y,y+h-1,-l)$。

一些要注意的地方都写在代码里了。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=20000+10; //双倍空间

int S[MAXN];
struct node {
    int x,y1,y2,w;
    bool operator <(const seg& rhs) const { //注意这个排序
        if (x!=rhs.x) return x<rhs.x;
        else return rhs.w>0;
    }
} p[MAXN];

struct Segment_Tree {
    int addv[MAXN<<2],maxv[MAXN<<2];
#define lson (o<<1)
#define rson (o<<1|1)
    inline void pushup(int o) { maxv[o]=max(maxv[lson],maxv[rson]); }
    inline void pushdown(int o) {
        if (addv[o]) {
            maxv[lson]+=addv[o],maxv[rson]+=addv[o];
            addv[lson]+=addv[o],addv[rson]+=addv[o];
            addv[o]=0;
        }
    }
    inline void init() {
        memset(addv,0,sizeof(addv));
        memset(maxv,0,sizeof(maxv));
    }
    inline void update(int o,int l,int r,int ql,int qr,int w) {
        if (ql<=l&&r<=qr) { maxv[o]+=w,addv[o]+=w; return; }
        int mid=(l+r)>>1;
        pushdown(o);
        if (ql<=mid) update(lson,l,mid,ql,qr,w);
        if (qr>mid) update(rson,mid+1,r,ql,qr,w);
        pushup(o);
    }
#undef lson
#undef rson
} T;

int main() {
    int Test=read();
    while (Test--) {
        T.init();
        int n=read(),W=read(),H=read();
        int tot=0,top=0;
        for (re int i=1;i<=n;++i) {
            int x=read(),y=read(),l=read();
            p[++tot]=(node){x,y,y+H-1,l};
            p[++tot]=(node){x+W,y,y+H-1,-l};
            S[++top]=y,S[++top]=y+H-1;
        }
        sort(S+1,S+top+1); sort(p+1,p+tot+1);
        top=unique(S+1,S+top+1)-S-1;
        int ans=0;
        for (re int i=1;i<=tot;++i) {
            int L=lower_bound(S+1,S+top+1,p[i].y1)-S;
            int R=lower_bound(S+1,S+top+1,p[i].y2)-S; //注意这里不用再-1
            T.update(1,1,top,L,R,p[i].w);
            ans=max(ans,T.maxv[1]);
        }
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 37 PM