题解：P1502 窗口的星星

· · 题解

题意简述

给定平面上 n 个点，求一个 w \times h 的矩形最多覆盖多少点权（边长平行于坐标轴，矩形不含边框，给出的是坐标系坐标）

n \le 10^4

思路

考虑一颗星星何时会产生贡献，即出现在矩形中，显然 x 坐标符合条件的矩形一定以其为右端点的一段区间，换句话说，只要窗户的右上角出现在一颗星星的右上角的一段区间里，这颗星星就会被覆盖，产生贡献。

考虑对于一颗星星 (x,y) 区间范围为 (x,y) \sim(x+w,y+h)，由于不算边框，故减去 1 为 (x,y) \sim(x+w-1,y+h-1)。而所有星星的区间会重合，只需要找到权最大的区间即可。

这样的问题可以直接用扫描线和线段树高效处理，对于一颗星星的区间加入就加上亮度值，退出就减掉，每次打擂台最后留下的就是最大值。

注意

code:

#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int maxn=100005;
long long t,n,w,h;
long long a[maxn<<1];//记得开long long 

struct node{
    long long l,r,sum;
    long long lazy;
}tr[maxn<<2];
struct STU{
    long long l,r,h,val;
    bool operator <(const STU&x)const{
        return (h!=x.h)?h<x.h:val>x.val;
    }//这段其实等价于cmp，后来去题解里学了一下重载运算符 
}line[maxn<<2];

void pushup(long long id){
    tr[id].sum=max(tr[lid].sum,tr[rid].sum);
}
void pushdown(long long id){
    if(tr[id].lazy){
        tr[lid].sum+=tr[id].lazy;
        tr[rid].sum+=tr[id].lazy;
        tr[lid].lazy+=tr[id].lazy;
        tr[rid].lazy+=tr[id].lazy;
        tr[id].lazy=0;
    }
}

void build(long long id,long long l,long long r){
    tr[id].l=l,tr[id].r=r;
    tr[id].sum=tr[id].lazy=0;
    if(l==r) return;
    long long mid=(l+r)/2;
    build(lid,l,mid);
    build(rid,mid+1,r);
    //这里扫描线时才加值，所以初始化为0即可 
}

void modify(long long id,long long l,long long r,long long v){
    if(tr[id].l>=l&&tr[id].r<=r){
        tr[id].lazy+=v;
        tr[id].sum+=v;
        return;
    }
    pushdown(id);
    long long mid=(tr[id].l+tr[id].r)/2;
    if(l<=mid) modify(lid,l,r,v);
    if(r>mid) modify(rid,l,r,v);
    pushup(id);
}
int main(){
    cin>>t;
    for(int q=1;q<=t;q++){
        cin>>n>>w>>h;
        memset(tr,0,sizeof(tr));
        memset(line,0,sizeof(line));
        memset(a,0,sizeof(a));
        for(long long i=1;i<=n;i++){
            long long x,y,l;
            cin>>x>>y>>l;
            a[i<<1-1]=y;
            a[i<<1]=y+h-1;
            line[i<<1-1].l=y;
            line[i<<1-1].r=y+h-1;
            line[i<<1-1].h=x;
            line[i<<1-1].val=l;
            line[i<<1].l=y;
            line[i<<1].r=y+h-1;line[i<<1].h=x+w-1;
            line[i<<1].val=-l; //每个星星的信息 
        }
        n*=2;
        sort(a+1,a+n+1);
        sort(line+1,line+n+1);
        long long num=unique(a+1,a+n+1)-a-1;//离散化 
        long long ans=0;
        build(1,1,num-1);
        for (long long i=1;i<=n;i++){
            long long l=lower_bound(a+1,a+num+1,line[i].l)-a-1;
            long long r=lower_bound(a+1,a+num+1,line[i].r)-a-1;
            modify(1,l,r,line[i].val);
            ans=max(ans,tr[1].sum);
        }
        cout<<ans<<endl;
    }
    return 0;
}