hdu 6638 Snowy Smile 线段树维护最大子段和

一个平面上有 n 个点，每个点有一个对应的权值，其他点的权值都是0，让你选一个矩形，要求矩形内所有点的权值最大。

枚举上边界，对于每一行的点，将他依此加入到线段树中，同时更新最大值。时间复杂度 

大力区间和并，查询的时候还要同时查一下跨左右区间的最大值。

#include <bits/stdc++.h>
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(que[k].l+que[k].r)/2;
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2005;
struct note
{
	int x;
	int y;
	ll val;
}in[MAXN];
int t1[MAXN], t2[MAXN];
struct node
{
	int l;
	int r;
	ll lmaxn;
	ll rmaxn;
	ll maxn;
	ll sum;
}que[MAXN * 4];
int n, qq1, qq2;
void up(int k)
{
	que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
	que[k].maxn = max({ que[k << 1].maxn,que[k << 1 | 1].maxn,que[k << 1].rmaxn + que[k << 1 | 1].lmaxn });
	que[k].lmaxn = max(que[k << 1].lmaxn, que[k << 1].sum + que[k << 1 | 1].lmaxn);
	que[k].rmaxn = max(que[k << 1 | 1].rmaxn, que[k << 1 | 1].sum + que[k << 1].rmaxn);
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	if (left == right)
	{
		que[k].sum = 0;
		que[k].maxn = 0;
		que[k].lmaxn = 0;
		que[k].rmaxn = 0;
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
void update(int pos, ll val, int k)
{
	if (que[k].l == que[k].r)
	{
		que[k].sum += val;
		que[k].maxn += val;
		que[k].lmaxn += val;
		que[k].rmaxn += val;
		return;
	}
	imid;
	if (pos <= mid)
		update(pos, val, k << 1);
	if (pos > mid)
		update(pos, val, k << 1 | 1);
	up(k);
}
ll queryl(int left, int right, int k)
{
	if (left == que[k].l && que[k].r == right)
		return que[k].lmaxn;
	imid;
	if (right <= mid)
		return queryl(left, right, k << 1);
	else if (left > mid)
		return queryl(left, right, k << 1 | 1);
	else
		return max({ queryl(lson), que[k << 1].maxn + queryl(rson) });
}
ll queryr(int left, int right, int k)
{
	if (left == que[k].l && que[k].r == right)
		return que[k].rmaxn;
	imid;
	if (right <= mid)
		return queryr(left, right, k << 1);
	else if (left > mid)
		return queryr(left, right, k << 1 | 1);
	else
		return max({ queryr(rson), queryr(lson) + que[k << 1 | 1].maxn });
}
ll query(int left, int right, int k)
{
	if (left == que[k].l && que[k].r == right)
		return que[k].maxn;
	imid;
	if (right <= mid)
		return query(left, right, k << 1);
	else if (left > mid)
		return query(left, right, k << 1 | 1);
	else
		return max({ query(lson),query(rson),queryr(lson) + queryl(rson) });
}
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d%d%lld", &in[i].x, &in[i].y, &in[i].val);
			t1[i] = in[i].x;
			t2[i] = in[i].y;
		}
		sort(t1 + 1, t1 + 1 + n);
		qq1 = unique(t1 + 1, t1 + 1 + n) - t1 - 1;
		for (int i = 1; i <= n; i++)
			in[i].x = lower_bound(t1 + 1, t1 + 1 + qq1, in[i].x) - t1;
		sort(t2 + 1, t2 + 1 + n);
		qq2 = unique(t2 + 1, t2 + 1 + n) - t2 - 1;
		for (int i = 1; i <= n; i++)
			in[i].y = lower_bound(t2 + 1, t2 + 1 + qq2, in[i].y) - t2;
		sort(in + 1, in + 1 + n, [](note q, note w) {
			if (q.y == w.y)
				return q.x < w.x;
			return q.y < w.y;
		});
		ll ans = 0;
		for (int i = 1; i <= qq2; i++)
		{
			build(1, qq1, 1);
			for (int j = 1; j <= n; j++)
			{
				if (in[j].y < i)
					continue;
				if (in[j].y != in[j - 1].y)
				{
					ll res = query(1, qq1, 1);
					ans = max(res, ans);
				}
				update(in[j].x, in[j].val, 1);
			}
			ll res = query(1, qq1, 1);
			ans = max(res, ans);
		}
		pr("%lld\n", ans);
	}
}
/*
1
9
1 1 1
1 2 1
1 3 1
2 1 1
2 2 -9
2 3 1
3 1 1
3 2 1
3 3 1
*/