题意简述
现在有有\(n\)颗星星,第\(i\)颗星星可以用三元组\((x_i,y_i,l_i)\)表示,意思是这颗星星在\((x_i,y_i)\)处,亮度为\(l_i\)。现在有一个\(w \times h\)的窗户,找一个合适的位置放置这个窗户,使其圈起来的星星亮度和最大。边框位置不算。
多组数据,\(T \le 10,n \le 10^4,W,H \le 10^6,0 \le x_i,y_i \le 2^{31}\)。
简单口胡
容易发现如果确定矩形的右上角的位置,那么这个矩形就是确定的。
于是我们考虑:
将每个星星作为左下角画一个\(W \times H\)的矩形,任何在这个矩形里的点,将其作为窗户的右上角来画窗户,则这个窗户一定能框这颗星星。
考虑到边界问题,我们将每颗星星向左下移动一格。用扫描线,将下底的权值设为\(l_i\),上底设为\(-l_i\),其实这里的“上底”应该是原来的上底再往上一个,因为处理完之后边界是可以停留的,所以应该再往上一个再减。
然后我们维护中间的最大值即可。
# include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
# define int long long
int Test;
int n,w,h;
struct Star
{
int x,y;
int l;
Star() {}
Star(int _x,int _y,int _l) : x(_x),y(_y),l(_l) {}
}a[N << 1];
struct Line
{
int y,x1,x2,d;
Line() {}
Line(int _y,int _x1,int _x2,int _d) : y(_y),x1(_x1),x2(_x2),d(_d) {}
}line[N << 1];
struct node
{
int Max,lazy;
}T[N << 3];
int b[N << 1];
bool compare(const struct Line &x,const struct Line &y)
{
if(x.y == y.y) return x.d < y.d;
return x.y < y.y;
}
void build(int root,int l,int r)
{
if(l == r)
{
T[root].Max = T[root].lazy = 0;
return;
}
int mid = (l + r) >> 1;
build(root << 1,l,mid);
build(root << 1 | 1,mid + 1,r);
T[root].Max = max(T[root << 1].Max,T[root << 1 | 1].Max);
T[root].lazy = 0;
return;
}
void pushdown(int root,int l,int r)
{
if(T[root].lazy == 0) return;
int mid = (l + r) >> 1,tag = T[root].lazy;
T[root << 1].lazy += tag;
T[root << 1 | 1].lazy += tag;
T[root << 1].Max += tag;
T[root << 1 | 1].Max += tag;
T[root].lazy = 0;
return;
}
void update(int root,int l,int r,int s,int t,int d)
{
if(l <= s && t <= r)
{
T[root].Max += d;
T[root].lazy += d;
return;
}
pushdown(root,s,t);
int mid = (s + t) >> 1;
if(l <= mid) update(root << 1,l,r,s,mid,d);
if(r > mid) update(root << 1 | 1,l,r,mid + 1,t,d);
T[root].Max = max(T[root << 1].Max,T[root << 1 | 1].Max);
return;
}
signed main(void)
{
scanf("%lld",&Test);
while(~scanf("%lld%lld%lld",&n,&w,&h))
{
for(int i = 1; i <= n; i++)
{
scanf("%lld %lld %lld",&a[i].x,&a[i].y,&a[i].l);
line[i * 2 - 1] = Line(a[i].y,a[i].x,a[i].x + w - 1,a[i].l);
line[i * 2] = Line(a[i].y + h,a[i].x,a[i].x + w - 1,-a[i].l);
b[i * 2 - 1] = a[i].x,b[i * 2] = a[i].x + w - 1;
}
n <<= 1;
sort(b + 1, b + n + 1);
sort(line + 1, line + n + 1, compare);
int L = unique(b + 1, b + n + 1) - b - 1;
build(1,1,L);
int ans = 0;
for(int i = 1; i <= n; i++)
{
line[i].x1 = lower_bound(b + 1, b + L + 1, line[i].x1) - b;
line[i].x2 = lower_bound(b + 1, b + L + 1, line[i].x2) - b;
update(1,line[i].x1,line[i].x2,1,L,line[i].d);
ans = max(ans,T[1].Max);
}
printf("%lld\n",ans);
}
return 0;
}