# 扫描线+线段树#4#5WA求救

@nwjxjrs 2021-03-25 23:58 回复
#include<iostream>
#include<algorithm>
#define MAXN 10000+5
using namespace std;
struct node1
{
long long x1, x2, y;
long long l;
}a[2 * MAXN];
struct node2
{
int left, right;
long long max;
long long tag;
}tree[16 * MAXN];//16?
long long qx[2 * MAXN] = { 0 };
bool cmp(node1 a, node1 b)
{
if (a.y == b.y)
return a.l > b.l;
return a.y < b.y;
}
void build(int o, int start, int end)
{
tree[o].left = start, tree[o].right = end;
tree[o].max = tree[o].tag = 0;
if (start == end)
return;
int mid = (start + end) / 2;
build(o * 2, start, mid);
build(o * 2 + 1, mid + 1, end);
}
{
if (tree[o].left != tree[o].right)
{
tree[o * 2].tag += tree[o].tag;
tree[o * 2 + 1].tag += tree[o].tag;
tree[o * 2].max += tree[o].tag;
tree[o * 2 + 1].max += tree[o].tag;
tree[o].tag = 0;
}
}
void add(int o, long long int start, long long int end, long long val)
{
if (tree[o].left == 0 && tree[o].right == 0)
return;
if (start > qx[tree[o].right + 1] || end < qx[tree[o].left])
return;
if (start <= qx[tree[o].left] && end >= qx[tree[o].right + 1])
{
tree[o].tag += val;
tree[o].max += val;
return;
}
int mid = (tree[o].left + tree[o].right) / 2;
add(o * 2, start, end, val);
add(o * 2 + 1, start, end, val);
tree[o].max = max(tree[o * 2].max, tree[o * 2 + 1].max);
}
int main(void)
{
int T;
cin >> T;
while (T--)
{
int n, w, h;
cin >> n >> w >> h;
for (int i = 1; i <= n; i++)
{
long long x, y, l;
cin >> x >> y >> l;
a[i] = { x,x + w - 1,y,l };
a[i + n] = { x,x + w - 1,y + h - 1,-l };
qx[i] = x;
qx[i + n] = x + w - 1;
}
sort(qx + 1, qx + 1 + 2 * n);
sort(a + 1, a + 1 + 2 * n, cmp);
int top = 2 * n;
build(1, 1, top - 1);
long long ans = 0;
for (int i = 1; i <= 2 * n; i++)
{
ans = max(ans, tree[1].max);
}
cout << ans << endl;
}
return 0;
}
@nwjxjrs 2021-03-26 00:01 回复 举报