很多题解都是简单带过，所以打算自己写一篇，顺便也加深自己理解
前置知识：线段树、线段树维护最大字段和、二维坐标离散化
题解：
1.很容易想到我们需要枚举所有子矩阵来得到一个最大子矩阵，所以我们的任务是 “枚举所有子矩阵”，
二维前缀和暴力枚举达到O(n^4), DP结合前缀和枚举也需要O(n^3)，然而我们的时间需要更少.
2.可以看到坐标范围为 -10^9~10^，但是点 n<=2000个，所以我们需要先将点 离散化。
3.将点 按y轴高度排序，枚举矩阵的上下界，这将达到O(n^2)了。
4.最重点的一步，将矩阵内的点 加入线段树维护。下面解释下这一步。
首先假设我们枚举的这一个矩阵的 上界为 up ,下界为 down ，目前的矩阵的宽度就已经知道是 up-down。
所以现在我们剩下的任务就是“枚举矩阵宽度” 来达到 “枚举宽度为up-down的所有子矩阵，找出宽度为up-down的最大子矩阵”。
我们宽度已知，所有要枚举也就是长度，这样我们可以把 “矩阵压缩称为一条线”。
这时候线段树的功能就能解决这个问题了。
用线段树来维护最大字段和，其实维护的是 “宽度为up-down”的最大矩阵和。
这样我们的时间复杂度就可以达到O(n^2 logn)了。
记得每次改变下界的时候要初始化线段树，关于这个初始化代码中还有一个小技巧，差不多减少了1.5s左右的时间。
#include <bits/stdc++.h> using namespace std;
typedef double dou;
typedef long long ll;
typedef pair<int, int> pii;
typedef map<int, int> mii; #define pai acos(-1.0)
#define M 4005
#define inf 0x3f3f3f3f
#define mod 1000000007
#define IN inline
#define left k<<1
#define right k<<1|1
#define lson L, mid, left
#define rson mid + 1, R, right
#define W(a) while(a)
#define lowbit(a) a&(-a)
#define ms(a,b) memset(a,b,sizeof(a))
#define Abs(a) (a ^ (a >> 31)) - (a >> 31)
#define false_stdio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) int T, n;
ll vx[M], vy[M];
ll xlen, ylen, pos, ans;
struct Data {
int x, y, val;
bool operator <(Data& t) {
return y < t.y;
}
}node[M];
struct Data_t {
ll sum;
ll Lmax, Rmax, Max;
}tree[M << ]; IN void Updata(int L, int R, int k, int id,int add) {
if (L == R) {
tree[k].sum += (ll)add;
tree[k].Lmax = tree[k].Rmax = tree[k].Max = tree[k].sum;
return;
}
int mid = L + R >> ;
if (id <= mid)Updata(lson, id, add);
else Updata(rson, id, add); //维护最大字段和
tree[k].sum = tree[left].sum + tree[right].sum;
tree[k].Lmax = max(tree[left].Lmax, tree[left].sum + tree[right].Lmax);
tree[k].Rmax = max(tree[right].Rmax, tree[right].sum + tree[left].Rmax);
tree[k].Max = max(max(tree[left].Max, tree[right].Max), tree[left].Rmax + tree[right].Lmax);
} int main() {
false_stdio;
cin >> T;
W(T--) {
cin >> n;
for (int i = ; i <= n; i++) {
cin >> node[i].x >> node[i].y >> node[i].val;
vx[i] = node[i].x, vy[i] = node[i].y;
} //二维坐标离散化
sort(vx + , vx + n + );
sort(vy + , vy + n + );
xlen = unique(vx + , vx + n + ) - vx - ;
ylen = unique(vy + , vy + n + ) - vy - ;
for (int i = ; i <= n; i++) {
node[i].x = lower_bound(vx + , vx + xlen + , node[i].x) - vx;
node[i].y = lower_bound(vy + , vy + ylen + , node[i].y) - vy;
}
sort(node + , node + n + ); ans = ; //首先枚举下界
for (int dw = ; dw <= ylen; dw++) {
pos = ;
memset(tree, , (xlen * + ) * sizeof(Data_t));//初始化线段树，离散化完有多少个点就初始化多大 W(node[pos].y < dw && pos <= n)pos++;//直接跳过小于下界的点 for (int up = dw; up <= ylen; up++) {//枚举上界
W(pos <= n && node[pos].y <= up) {//将上界与下届之间的点加入线段树中
Updata(, xlen, , node[pos].x, node[pos].val);
pos++;
}
ans = max(ans, tree[].Max);
}
}
cout << ans << endl;
}
return ;
}