C++ 代码

//1.因为我们已经知道了矩形的长和宽，所以对于任意一个星星(x, y, c), 都可以得到一个确切的矩形，所以每一个星星，我们建立一个固定大小的
//  矩形，矩形的左下角为(x, y), 因为边界上的星星不算,所以右上角表示为(x + w, y + h - 1),目标是求出固定矩形区域内的最大值
//2.所以这道题我们可以用扫描线来做,取出每个区域的左右边界,保存俩个四元组(x, y, y + h - 1, c), (x + w, y, y + h - 1, -c)
//  并将这些四元组按照x坐标排序
//3.同时用线段树来维护纵坐标的区间最大值, 逐一扫描四元组(x, y1, y2, c), 并执行线段树的修改操作,将[y1, y2]区间上的值都加上c, 不断向上
//  更新父节点最大值,然后得到根节点的dat值得到最终的答案

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 20010;
struct node{  //存四元组
    int x, y1, y2, dat;
}a[N * 2];
struct p{   //树
    int l, r;
    ll dat, add;
}t[N * 4];
int mp[N];
bool cmp(node a, node b)  //将x坐标从小到大排序
{
    if(a.x == b.x)return a.dat < b.dat;
    return a.x < b.x;
}
void build(int p, int l, int r)  //建树
{
    t[p].l =l, t[p].r = r;
    t[p].add = 0, t[p].dat = 0;
    if(l == r)return ;
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
}
void spread(int p)  //表示p节点已经被修改，但子节点还没有被修改
{
    //修改子节点，并给子节点打延迟标记
    t[p * 2].dat += t[p].add;
    t[p * 2 + 1].dat += t[p].add;
    t[p * 2].add += t[p].add;
    t[p * 2 + 1].add += t[p].add;
    t[p].add = 0;  //清除p的标记
}
//线段树维护的内容是在区间1 ~ m内,区域(x, y) ~ (x + w, y + h)亮度的最大值
void change(int p, int l, int r, int x)
{
    if(l <= t[p].l && r >= t[p].r){
        t[p].add += x;
        t[p].dat += x;
        return ;
    }
    if(t[p].add)spread(p);//延迟标记
    int mid =(t[p].l + t[p].r) / 2;
    if(l <= mid) change(p * 2, l, r, x);
    if(r > mid) change(p * 2 + 1, l, r, x);
    t[p].dat = max(t[p * 2].dat, t[p * 2 + 1].dat); //更新节点
}
int main()
{
    int n, w, h, x, y, c;
    while(scanf("%d%d%d",&n, &w, &h) != EOF){
        int num = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d", &x, &y, &c);
            //矩形边界上的星星不算，所以将矩形的上边界减1
            a[++num] = {x, y, y + h - 1, c};    
            mp[num] = y;
            a[++num] = {x + w, y, y + h - 1, -c};
            mp[num] = y + h - 1;
        }
        sort(mp + 1, mp + 1 + num);
        int m = unique(mp + 1, mp + 1 + num) - mp - 1; //离散化 + 去重
        for(int i = 1; i <= num; i++){  //预处理出所有坐标离散化之后的结果
            a[i].y1 = lower_bound(mp + 1, mp + 1 + m, a[i].y1) - mp;
            a[i].y2 = lower_bound(mp + 1, mp + 1 + m, a[i].y2) - mp;
        }
        sort(a + 1, a + 1 + num, cmp);
        build(1, 1, m);  //建树
        ll ans = 0;
        for(int i = 1; i <= num; i++){
            change(1, a[i].y1, a[i].y2, a[i].dat);  
            ans = max(ans, t[1].dat);
        }
        cout << ans << endl;
    }
    return 0;
}