Solution 窗口的星星

扫描线

分析：

首先不能在边界上比较毒瘤

假设矩形左下角坐标为\((x,y)\)，给定宽\(W\)高\(H\)那么右上角坐标就是\((x+W,y+H)\)，我们要使得点不能在边界上，可以等价于把每个点向左下方平移\(0.5\)个单位，矩形的顶点位于整点上。这个时候相当于左下角\((x,y)\)，右下角\((x+W-1,y+H-1)\)

然后我们来看怎么统计的问题，这个可以用扫描线来做

我们用一棵线段树来维护纵轴

左下角的点加入了就相当于对\([y,y+H-1]\)这一段内所有点（对应在坐标系上就是平行于\(x\)轴的线）的贡献增加了给定的权值\(c\)，右上角删除同理，离散化后就可以方便的用线段树维护了

我们按照\(x\)坐标排序即可，注意判断有多个点在一条平行于\(y\)轴的直线上的情况

有一个坑，\(y+W-1\)可能爆\(int\)，要开\(unsigned\;int\)

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 1e5;
typedef unsigned int uint;
namespace ST{
    #define lson (root << 1)
    #define rson (root << 1 | 1)
    struct Node{
        int l,r,val,mark;
    }tree[maxn << 2];
    inline void build(int a,int b,int root = 1){
        tree[root].l = a;
        tree[root].r = b;
        tree[root].val = tree[root].mark = 0;
        if(a == b)return;
        int mid = (a + b) >> 1;
        build(a,mid,lson);
        build(mid + 1,b,rson);
    }
    inline void pushup(int root){tree[root].val = max(tree[lson].val,tree[rson].val);}
    inline void pushdown(int root){
        tree[lson].mark += tree[root].mark;
        tree[rson].mark += tree[root].mark;
        tree[lson].val += tree[root].mark;
        tree[rson].val += tree[root].mark;
        tree[root].mark = 0;
    }
    inline void modify(int a,int b,int val,int l,int r,int root = 1){
        if(a <= l && b >= r){
            tree[root].val += val;
            tree[root].mark += val;
            return;
        }
        pushdown(root);
        int mid = (l + r) >> 1;
        if(a <= mid)modify(a,b,val,l,mid,lson);
        if(b >= mid + 1)modify(a,b,val,mid + 1,r,rson);
        pushup(root);
    }
    inline int query(){return tree[1].val;}

}
struct Modi{
    uint x,y1,y2;
    int c;
    bool operator < (const Modi &rhs)const{
        return x < rhs.x;
    }
}modi[maxn];
int n,W,H,siz,modi_tot;
uint x,y,tmp[maxn];
inline void solve(){
    modi_tot = siz = 0;
    for(int c,i = 1;i <= n;i++){
        scanf("%u %u %d",&x,&y,&c);
        modi[++modi_tot] = (Modi){x,y,y + H - 1,c};
        modi[++modi_tot] = (Modi){x + W,y,y + H - 1,-c};
        tmp[++siz] = y;
        tmp[++siz] = y + H - 1;
    }
    sort(tmp + 1,tmp + 1 + siz);
    siz = unique(tmp + 1,tmp + 1 + siz) - tmp - 1;
    for(int i = 1;i <= modi_tot;i++)
        modi[i].y1 = lower_bound(tmp + 1,tmp + 1 + siz,modi[i].y1) - tmp,modi[i].y2 = lower_bound(tmp + 1,tmp + 1 + siz,modi[i].y2) - tmp;
    ST::build(1,siz);
    sort(modi + 1,modi + 1 + modi_tot);
    int ans = 0;
    for(int i = 1;i <= modi_tot;i++){
        ST::modify(modi[i].y1,modi[i].y2,modi[i].c,1,siz);
        while(i < modi_tot && modi[i].x == modi[i + 1].x){
            i++;
            ST::modify(modi[i].y1,modi[i].y2,modi[i].c,1,siz);
        }
        ans = max(ans,ST::query());
    }
    printf("%d\n",ans);
}
int t;
int main(){
    scanf("%d",&t);
    while(t--)scanf("%d %d %d",&n,&W,&H),solve();
    return 0;
}

左下

题解 P1502 【窗口的星星】

Solution 窗口的星星