萌新有个疑问求解答
查看原帖
萌新有个疑问求解答
815504
chenwenmo楼主2024/7/17 15:40

设星星的坐标是(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;
}
2024/7/17 15:40
加载中...