设星星的坐标是(x, y)1.
窗户宽为W,高为H
如果把窗户的移动看成窗户右上角的移动
那能框住这颗星星的窗户的右上角移动范围应该是
(x + 1, y + 1)到(x + W - 1, y + H - 1)这个范围的矩形吧?
那为什么写代码在添加矩形的边的时候x和y不用加一呢
附代码\
#include<bits/stdc++.h>
#define y1 other
using namespace std;
typedef long long ll;
const int N = 10010;
int T;
ll n, W, H;
ll val[N << 1], m;
struct line{
ll x, y1, y2, k;
}l[N << 1];
bool cmp(line a, line b) {return a.x == b.x ? a.k > b.k : a.x < b.x;}
struct tree{
int l, r;
ll maxn, add;
}t[N << 3];
void build(int x, int l, int r){
t[x].l = l;
t[x].r = r;
t[x].maxn = t[x].add = 0;
if(l == r) return;
int mid = l + r >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
}
void push_up(int x){
t[x].maxn = max(t[x << 1].maxn, t[x << 1 | 1].maxn);
}
void push_down(int x){
if(t[x].add){
int l = x << 1, r = x << 1 | 1;
t[l].add += t[x].add;
t[r].add += t[x].add;
t[l].maxn += t[x].add;
t[r].maxn += t[x].add;
t[x].add = 0;
}
}
void update(int x, int l, int r, ll k){
if(t[x].l >= l && t[x].r <= r){
t[x].add += k;
t[x].maxn += k;
return;
}
push_down(x);
int mid = t[x].l + t[x].r >> 1;
if(l <= mid) update(x << 1, l, r, k);
if(r > mid) update(x << 1 | 1, l, r, k);
push_up(x);
}
int find(ll x){
return lower_bound(val + 1, val + 1 + m, x) - val;
}
int main(){
scanf("%d", &T);
while(T--){
m = 0;
memset(val, 0, sizeof(val));
ll x, y, k;
scanf("%lld%lld%lld", &n, &W, &H);
for(int i = 1, j = 0; i <= n; i++){
scanf("%lld%lld%lld", &x, &y, &k);
l[++j] = (line){x, y, y + H - 1, k};
l[++j] = (line){x + W - 1, y, y + H - 1, -k};
val[++m] = y;
val[++m] = y + H - 1;
}
sort(val + 1, val + 1 + m);
m = unique(val + 1, val + 1 + m) - val - 1;
sort(l + 1, l + 1 + 2 * n, cmp);
build(1, 1, m);
ll ans = -1;
for(int i = 1; i <= 2 * n; i++){
update(1, find(l[i].y1), find(l[i].y2), l[i].k);
ans = max(ans, t[1].maxn);
}
printf("%lld\n", ans);
}
return 0;
}