Snowy Smile HDU - 6638（扫描线，线段树区间合并）

本文主要是介绍Snowy Smile HDU - 6638（扫描线，线段树区间合并），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

There are n pirate chests buried in Byteland, labeled by 1,2,…,n. The i-th chest’s location is (xi,yi), and its value is wi, wi can be negative since the pirate can add some poisonous gases into the chest. When you open the i-th pirate chest, you will get wi value.

You want to make money from these pirate chests. You can select a rectangle, the sides of which are all paralleled to the axes, and then all the chests inside it or on its border will be opened. Note that you must open all the chests within that range regardless of their values are positive or negative. But you can choose a rectangle with nothing in it to get a zero sum.

Please write a program to find the best rectangle with maximum total value.
Input
The first line of the input contains an integer T(1≤T≤100), denoting the number of test cases.

In each test case, there is one integer n(1≤n≤2000) in the first line, denoting the number of pirate chests.

For the next n lines, each line contains three integers xi,yi,wi(−109≤xi,yi,wi≤109), denoting each pirate chest.

It is guaranteed that ∑n≤10000.
Output
For each test case, print a single line containing an integer, denoting the maximum total value.
Sample Input
2
4
1 1 50
2 1 50
1 2 50
2 2 -500
2
-1 1 5
-1 1 1
Sample Output
100
6

题意：
平面上很多个带权点，求一个矩阵覆盖一些点使得权值和最大。

思路：
$n$ 的范围只有2000，所以可以枚举矩阵的下边界（ $y$ 轴）。然后每次将矩阵上边界移动一个单位（离散化后的单位）。线段树维护每个点在 $x$ 轴上的位置，维护一下最大值，就得到了当前的最大权值矩阵。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>using namespace std;typedef long long ll;
const int maxn = 4e3 + 7;
struct Node {int x,y,w;
}a[maxn];
vector<pair<int,int> >vec[maxn];struct Tree {int l,r;ll sum;ll mx,lmx,rmx;
}t[maxn << 2];void pushup(int i) {t[i].mx = max(max(t[i * 2].mx,t[i * 2 + 1].mx),t[i * 2].rmx + t[i * 2 + 1].lmx);t[i].sum = t[i * 2].sum + t[i * 2 + 1].sum;t[i].lmx = max(t[i * 2].lmx,t[i * 2].sum + t[i * 2 + 1].lmx);t[i].rmx = max(t[i * 2 + 1].rmx,t[i * 2 + 1].sum + t[i * 2].rmx);
}void build(int i,int l,int r) {t[i].l = l;t[i].r = r;if(l == r) {t[i].sum = t[i].mx = t[i].lmx = t[i].rmx = 0;return;}int m = (l + r) >> 1;build(i * 2,l,m);build(i * 2 + 1,m + 1,r);pushup(i);
}void update(int i,int x,int v) {if(t[i].l == t[i].r) {t[i].sum += v;t[i].lmx += v;t[i].rmx += v;t[i].mx += v;return;}int m = (t[i].l + t[i].r) >> 1;if(x <= m) update(i * 2,x,v);if(x > m)  update(i * 2 + 1,x,v);pushup(i);
}int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);vector<int>vecx,vecy;for(int i = 1;i <= n;i++) {scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);vecx.push_back(a[i].x);vecy.push_back(a[i].y);vec[i].clear();}sort(vecx.begin(),vecx.end());sort(vecy.begin(),vecy.end());vecx.erase(unique(vecx.begin(),vecx.end()),vecx.end());vecy.erase(unique(vecy.begin(),vecy.end()),vecy.end());for(int i = 1;i <= n;i++) {a[i].x = lower_bound(vecx.begin(),vecx.end(),a[i].x) - vecx.begin() + 1;a[i].y = lower_bound(vecy.begin(),vecy.end(),a[i].y) - vecy.begin() + 1;vec[a[i].y].push_back({a[i].x,a[i].w});}ll ans = 0;for(int i = 1;i <= vecy.size();i++) { //矩阵下界build(1,1,vecy.size());for(int j = i;j <= vecy.size();j++) { //矩阵上界for(int k = 0;k < vec[j].size();k++) {int pos = vec[j][k].first,val = vec[j][k].second;update(1,pos,val);}ans = max(ans,t[1].mx);}}printf("%lld\n",ans);}return 0;
}