扫描线+线段树#4#5WA求救
查看原帖
扫描线+线段树#4#5WA求救
416483
Niouville楼主2021/3/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);
}
void spread(int o)
{
	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;
	}
	spread(o);
	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++)
		{
			add(1, a[i].x1, a[i].x2, a[i].l);
			ans = max(ans, tree[1].max);
		}
		cout << ans << endl;
	}
	return 0;
}
2021/3/25 23:58
加载中...