题目链接
把每个星星作为左下角，做出长为\(w-0.5\)，宽为\(h-0.5\)的矩形。
\(-0.5\)是因为边框上的不算。
离散化\(y\)坐标。
记录\(2n\)个\(4\)元组\((x,y1,y2,light)\)，\(light\)指这颗星星的亮度，左正右负。
然后线段树每次在\([y1,y2]\)上加上\(light\)，维护最大值即可。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define re register
using namespace std;
inline int read(){
re int s = 0, w = 1;
re char ch = getchar();
while(ch < '0' || ch > '9'){ ch = getchar(); if(ch == '-') w = -1; }
while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }
return s * w;
}
const int MAXN = 100010 << 2;
struct lsh{
double val;
int id, type;
int operator < (const lsh A) const{
return val < A.val;
}
}p[MAXN];
struct node{
double x;
int y[2], light;
int operator < (const node A) const{
return x < A.x || x == A.x && light < A.light;
}
}q[MAXN];
int dat[MAXN], lazy[MAXN], n, w, h, T, num, tot, ans;
#define lc (now << 1)
#define rc (now << 1 | 1)
inline void pushup(int now){
dat[now] = max(dat[lc], dat[rc]);
}
inline void pushdown(int now){
if(lazy[now]){
lazy[lc] += lazy[now]; lazy[rc] += lazy[now];
dat[lc] += lazy[now]; dat[rc] += lazy[now];
lazy[now] = 0;
}
}
void update(int now, int l, int r, int wl, int wr, int p){
if(l >= wl && r <= wr){ lazy[now] += p; dat[now] += p; return; }
if(l > wr || r < wl) return;
pushdown(now);
int mid = (l + r) >> 1;
update(lc, l, mid, wl, wr, p);
update(rc, mid + 1, r, wl, wr, p);
pushup(now);
}
int main(){
T = read(); p[0].val = -233;
while(T--){
n = read(); w = read(); h = read(); num = tot = ans = 0;
for(int i = 1; i <= n; ++i){
q[i].x = read(); p[++num].val = read(); q[i].light = read();
p[num].id = i; p[num].type = 0;
p[++num].id = i; p[num].val = 1.0 * p[num - 1].val + h - 0.5; p[num].type = 1;
}
sort(p + 1, p + num + 1);
for(int i = 1; i <= num; ++i)
if(fabs(p[i].val - p[i - 1].val) > 1e-8)
q[p[i].id].y[p[i].type] = ++tot;
else q[p[i].id].y[p[i].type] = tot;
for(int i = 1; i <= n; ++i){
q[i + n] = q[i];
q[i + n].light *= -1;
q[i + n].x = 1.0 * q[i].x + w - 0.5;
}
n <<= 1;
sort(q + 1, q + n + 1);
for(int i = 1; i <= n; ++i){
update(1, 1, tot, q[i].y[0], q[i].y[1], q[i].light);
ans = max(ans, dat[1]);
}
printf("%d\n", ans);
memset(lazy, 0, sizeof lazy); memset(dat, 0, sizeof dat);
}
}