@nwjxjrs 2021-03-14 15:00 回复 #include<iostream> #include<algorithm> #include<cstdio> using namespace std; struct node1 { long long x, y, l; long long left, right; }star[10005]; long long height_sorted[10005] = { 0 }, height_set[10005] = { 0 }, ans = 0; struct node2 { int left; int right; long long val = 0; long long lazy_tag = 0; }tree[4 * 10005]; bool cmp_x(node1 a, node1 b) { return a.x < b.x; } void build(int num, int start, int end) { tree[num].left = start, tree[num].right = end; if (start == end) { tree[num].val = 0; return; } int mid = (tree[num].left + tree[num].right) / 2; build(num * 2, start, mid); build(num * 2 + 1, mid + 1, end); } void spread(int num) { if (tree[num].lazy_tag) { tree[num * 2].val += tree[num].lazy_tag; tree[num * 2 + 1].val += tree[num].lazy_tag; tree[num * 2].lazy_tag += tree[num].lazy_tag; tree[num * 2 + 1].lazy_tag += tree[num].lazy_tag; tree[num].lazy_tag = 0; } } void change(int num, int start, int end, long long int value) { if (start <= tree[num].left && end >= tree[num].right) { tree[num].val += value; tree[num].lazy_tag += value; return; } spread(num); int mid = (tree[num].left + tree[num].right) / 2; if (start <= mid)change(num * 2, start, end, value); if (end > mid)change(num * 2 + 1, start, end, value); tree[num].val = max(tree[num * 2].val, tree[num * 2 + 1].val); } int main(void) { int T; scanf("%d", &T); for (int k = 1; k <= T; k++) { //initial: int n, w, h;int top = 0; scanf("%d%d%d", &n, &w, &h); for (int i = 1; i <= n; i++) { scanf("%lld%lld%lld", &star[i].x, &star[i].y, &star[i].l); height_sorted[i] = star[i].y; } sort(star + 1, star + 1 + n, cmp_x); sort(height_sorted + 1, height_sorted + n + 1); for (int i = 1; i <= n; i++) { if (i == 1 || height_sorted[i] ^ height_sorted[i - 1]) height_set[++top] = height_sorted[i]; } for (int i = 1; i <= n; i++) { star[i].left = lower_bound(height_set + 1, height_set + 1 + top, star[i].y) - height_set; star[i].right = lower_bound(height_set + 1, height_set + 1 + top, star[i].y + h) - height_set - 1; } build(1, 1, top); //work: int tail = 1; for (int i = 1; i <= n; i++) { long long int j = star[i].x; while (star[i].x == j) { change(1, star[i].left, star[i].right, star[i].l); i++; } i--; while (tail < i && star[tail].x + w <= j) { change(1, star[tail].left, star[tail].right, -star[tail].l); tail++; } ans = max(ans, tree[1].val); } printf("%lld\n", ans); } return 0; }