杭电多校第六场的第五题
这个题目WA了我一天，因为思路和题解的不一样，一直以为是思路错了，结果最后发现居然是线段树写错了，真的是佛了。
Snowy Smile
Time Limit: 4000/4000 MS (Java/Others) Memory Limit: 524288/524288
K (Java/Others) Total Submission(s): 2640 Accepted Submission(s):
225
Problem Description
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
分析
给你2000个带权点，用矩形来框住这些点，求最大的收益。
因为每个点的x和y坐标的范围是1e9，所以第一步要先进行离散化把点映射到1-2000之间。之后问题就转化成了一个最大子矩阵和的问题。
这里如果直接求最大子矩阵，最好的复杂度是dp，O(n^3)，还是会超时。
因为这里只有2000个点，所以我们可以利用线段树动态加点求最大子段和来使得复杂度优化到O(n^2lgn)。
具体的做法我和题解的不大一样，我是这样做的。
- 离散化x坐标和y坐标，并最终按照y坐标的大小来排序。
- 枚举上边界（此处为一个n），并初始化线段树
- 每次加入一行点（也可以理解为控制下边界，为另一个n）
- 询问当前所加入的点的最大子段和，更新答案
参考代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define MAXN 2005
typedef long long ll;
using namespace std;struct node {
int x,nx,y,ny;ll w;
}a[MAXN];ll sum[MAXN<<2],msum[MAXN<<2],lsum[MAXN<<2],rsum[MAXN<<2];void pushup(int rt) {
sum[rt]=sum[rt<<1]+sum[rt<<1|1];msum[rt]=max(msum[rt<<1],msum[rt<<1|1]);msum[rt]=max(msum[rt],rsum[rt<<1]+lsum[rt<<1|1]);lsum[rt]=max(lsum[rt<<1],sum[rt<<1]+lsum[rt<<1|1]);rsum[rt]=max(rsum[rt<<1|1],sum[rt<<1|1]+rsum[rt<<1]);
}void build(int l,int r,int rt) {
sum[rt]=msum[rt]=lsum[rt]=rsum[rt]=0;if (l==r) {
return;}int m=(l+r)>>1;build(lson);build(rson);
}void update(int p,ll c,int l,int r,int rt) {
if (l==r) {
lsum[rt]=rsum[rt]=msum[rt]=sum[rt]=sum[rt]+c;return;}int m=(l+r)>>1;if (p<=m) update(p,c,lson);if (p>m) update(p,c,rson);pushup(rt);
}bool cmpx(node a1,node a2) {
if (a1.x==a2.x)return a1.y<a2.y;return a1.x<a2.x;
}bool cmpy(node a1,node a2) {
if (a1.y==a2.y)return a1.x<a2.x;return a1.y<a2.y;
}int T,n,sx,sy;int main() {
scanf("%d",&T);while(T--) {
sx=sy=0;scanf("%d",&n);for (int i=1;i<=n;i++) {
scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].w);}// 离散化x坐标sort(a+1,a+1+n,cmpx);for (int i=1;i<=n;i++) {
if (i==1 || (a[i].x!=a[i-1].x)) {
a[i].nx=++sx;} else {
a[i].nx=a[i-1].nx;}}// 离散化y坐标sort(a+1,a+1+n,cmpy);for (int i=1;i<=n;i++) {
if (i==1 || (a[i].y!=a[i-1].y)) {
a[i].ny=++sy;} else {
a[i].ny=a[i-1].ny;}}ll ans=0;// 枚举上边界for (int i=1;i<=sy;i++) {
// 建空树build(1,n,1);for (int j=1;j<=n;j++) {
// 加点if (a[j].ny>=i) {
update(a[j].nx,a[j].w,1,n,1);}// 加入一行点后更新答案if (j==n || a[j+1].ny!=a[j].ny) {
ans=max(ans,msum[1]);}}}cout << ans << endl;}return 0;
}