扫描线 + 线段树 + 延迟标记
1. 一个框要圈住某颗星星就有一定的范围，将这个范围交起来，就是能圈住这些星星的框的范围。
2. 将这些框都设一个值为这颗星星的亮度 c，若某个范围有重叠，那么这个范围的亮度 c 就可以叠加。只需要对这所有框从头扫描一遍，找出重叠值最大的即可，用扫描线处理。
3. 用线段树 + 延迟标便可以快速找出最大的。
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e4 + 10;
struct xin {
int x, y1, y2, c;
bool operator < (const xin &a) {
return x < a.x || (x == a.x && c > a.c);
}
} a[N * 2];
struct node {
int l, r;
int dat, add;
} t[N * 8];
int n, w, h;
int b[N * 2], c[N * 2];
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r, t[p].dat = 0, t[p].add = 0;
if(l == r) return;
int mid = l + r >> 1;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
}
void spread(int p) {
if(t[p].add) {
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;
}
}
void change(int p, int l, int r, int d) {
if(l <= t[p].l && r >= t[p].r) {
t[p].dat += d;
t[p].add += d;
return;
}
spread(p);
int mid = t[p].l + t[p].r >> 1;
if(l <= mid) change(p * 2, l, r, d);
if(r > mid) change(p * 2 + 1, l, r, d);
t[p].dat = max(t[p * 2].dat, t[p * 2 + 1].dat);
}
int ask(int p, int l, int r) {
if(l <= t[p].l && r >= t[p].r) return t[p].dat;
spread(p);
int mid = t[p].l + t[p].r >> 1, val = 0;
if(l <= mid) val += ask(p * 2, l, r);
if(r > mid) val += ask(p * 2 + 1, l, r);
return val;
}
signed main() {
while(cin >> n >> w >> h) {
for(int i = 1; i <= n; i++) {
int x, y, c;
cin >> x >> y >> c;
a[i * 2 - 1] = {x, y, y + h - 1, c};
a[i * 2] = {x + w - 1, y, y + h - 1, -c};
b[i * 2 - 1] = y;
b[i * 2] = y + h - 1;
}
sort(b + 1, b + n * 2 + 1);
int k = unique(b + 1, b + n * 2 + 1) - b - 1;
sort(a + 1, a + n * 2 + 1);
int ans = 0;
build(1, 1, k);
for(int i = 1; i <= n * 2; i++) {
int y1 = lower_bound(b + 1, b + k + 1, a[i].y1) - b;
int y2 = lower_bound(b + 1, b + k + 1, a[i].y2) - b;
change(1, y1, y2, a[i].c);
ans = max(ans, ask(1, 1, k));
}
cout << ans << endl;
}
return 0;
}
