原题链接 窗口的星星

题目描述

晚上，小卡从阳台望出去，“哇~~~~好多星星啊”，但他还没给其他房间设一个窗户。

天真的小卡总是希望能够在晚上能看到最多最亮的星星，但是窗子的大小是固定的，边也必须和地面平行。

这时小卡使用了超能力（透视术）知道了墙后面每个星星的位置和亮度，但是小卡发动超能力后就很疲劳，只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。

输入格式

本题有多组数据，第一行为$T$，表示有$T$组数据。

对于每组数据：

第一行 $3$ 个整数 $n,W,H $表示有 $n$ 颗星星，窗口宽为 $W$，高为 $H$。

接下来 $n$ 行，每行三个整数$x_i,y_i,l_i$表示星星的坐标在$(x_i,y_i)$，亮度为$l_i$。

输出格式

$T$个整数，表示每组数据中窗口星星亮度总和的最大值。

说明

小卡买的窗户框是金属做的，所以在边框上的不算在内。

数据范围

$1≤T≤10$
$1≤n≤10^4$
$1≤W,H≤10^6，0≤x_i,y_i<2^{31}$

题目分析

在一个直角坐标系上一些点（星星），然后每个点有个权值（亮度）。给你一个矩形（窗户）的长宽，求出矩形覆盖点权值和的最大值。
我们把星星看成一个矩形（长宽取窗户长宽）的左下角点，然后只要枚举窗户右上角，只要窗户右上角的点在矩形内，矩形（窗户）就可以覆盖点（星星），就可以有以下转化面积覆盖点->点在面积内，然后就可以线段树+扫描线

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=10010;
typedef long long ll;
int n,w,h;
struct seg
{
    ll x,y1,y2,val;
    bool operator <(const seg &a) const
    {
        if(x==a.x) return val>a.val;//保证先加后减
        return x<a.x;
    }
}line[2*N];
struct node
{
    int l,r;
    ll val,lazy;//维护区间最值
}tree[N<<3];
vector<ll> ys;
int find(int x)
{
    return lower_bound(ys.begin(),ys.end(),x)-ys.begin();
}
void pushup(int u)
{
    tree[u].val=max(tree[u<<1].val,tree[u<<1|1].val);
}
void build(int u,int l,int r)
{
    tree[u]={l,r,0,0};
    if(l==r) return;
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void pushdown(int u)
{
    tree[u<<1].lazy+=tree[u].lazy;
    tree[u<<1|1].lazy+=tree[u].lazy;
    tree[u<<1].val+=tree[u].lazy;
    tree[u<<1|1].val+=tree[u].lazy;
    tree[u].lazy=0;
}
void modify(int u,int l,int r,int x)
{
    if(tree[u].l>=l&&tree[u].r<=r)
    {
        tree[u].lazy+=x;
        tree[u].val+=x; 
        return;
    }
    pushdown(u);
    int mid=tree[u].l+tree[u].r>>1;
    if(l<=mid) modify(u<<1,l,r,x);
    if(r>mid) modify(u<<1|1,l,r,x);
    pushup(u);
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>w>>h;
        h--,w--;//窗户边界不算直接减一
        int x,y,val;
        ys.clear();
        memset(tree,0,sizeof tree);
        for(int i=0,j=0;i<n;i++)
        {
            cin>>x>>y>>val;
            line[j++]={x,y,y+h,val};
            line[j++]={x+w,y,y+h,-val};
            ys.push_back(y),ys.push_back(y+h);
        }
        sort(ys.begin(),ys.end());
        ys.erase(unique(ys.begin(),ys.end()),ys.end());
        sort(line,line+2*n);
        ll res=0;
        build(1,0,ys.size()-1);
        for(int i=0;i<2*n;i++)
        {
            int y1=find(line[i].y1),y2=find(line[i].y2),val=line[i].val;
            modify(1,y1,y2,val);
            res=max(res,tree[1].val);
        }
        cout<<res<<endl;
    }
    return 0;
}

感想

就这题做了一上午，我🤮了，还是太菜~-~！