题意：

求一个子矩阵要求其矩阵内的合最大。

题解：

正常的求最大子矩阵的复杂度是O(n^3)

对于这一题说复杂度过不去，注意到这个题总共只有2000个点关键点在与这里优化

最大子矩阵可以压缩矩阵变成最大字段和问题

然后可以通过带修改的最大字段和维护这2000个点，复杂度就变成了了O(n^2logn)

将算出每一列的合的操作 用待修改的最大字段和的线段树维护。

#include
#include
#include
#include
#include
#include
#include
#include

} Tree[maxn << ]; void updata ( int rt ) { Tree[rt].maxx = max ( Tree[rtl].maxx, max ( Tree[rtr].maxx, Tree[rtl].vr + Tree[rtr].vl ) ); Tree[rt].sum = Tree[rtl].sum + Tree[rtr].sum; Tree[rt].vl = max ( Tree[rtl].vl, Tree[rtl].sum + Tree[rtr].vl ); Tree[rt].vr = max ( Tree[rtr].vr, Tree[rtr].sum + Tree[rtl].vr ); } void build ( int l, int r, int rt ) { Tree[rt].fg = true; if ( l == r ) { Tree[rt].sum = s[l]; Tree[rt].maxx = s[l]; Tree[rt].vl = s[l]; Tree[rt].vr = s[l]; return ; } int mid = ( l + r ) >> ;
build ( l, mid, rtl );
build ( mid + , r, rtr );
updata ( rt );
}
void add ( int l, int r, int rt, int pos, int to ) {
if ( l > pos || r < pos ) return ; if ( l == r ) { Tree[rt].sum += to; Tree[rt].maxx += to; Tree[rt].vl += to; Tree[rt].vr += to; return ; } int mid = ( l + r ) >> ;
add ( l, mid, rtl, pos, to );
add ( mid + , r, rtr, pos, to );
updata ( rt );
}
Segtree query ( int l, int r, int rt, int sa, int se ) {
if ( sa <= l && r <= se ) return Tree[rt]; int mid = ( l + r ) >> ;
if ( sa > mid ) return query ( mid + , r, rtr, sa, se );
if ( se <= mid ) return query ( l, mid, rtl, sa, se ); Segtree t, lson, rson; lson = query ( l, mid, rtl, sa, se ); rson = query ( mid + , r, rtr, sa, se ); t.vl = max ( lson.vl, lson.sum + rson.vl ); t.vr = max ( rson.vr, lson.vr + rson.sum ); t.maxx = max ( lson.vr + rson.vl, max ( lson.maxx, rson.maxx ) ); return t; } vectorv[maxn];
int main() {
// FIN;
sf ( T );
while ( T-- ) {
sf ( n );
for ( int i = ; i <= n ; i++ ) {
scanf ( "%lld%lld%lld", &x[i], &y[i], &w[i] );
a[i] = x[i], b[i] = y[i];
v[i].clear();
}
sort ( a + , a + + n ), sort ( b + , b + + n );
int len1 = unique ( a + , a + + n ) - a - ;
int len2 = unique ( b + , b + + n ) - b - ;
for ( int i = ; i <= n ; i++ ) for ( int j = ; j <= n ; j++ ) mp[i][j] = ;
for ( int i = ; i <= n ; i++ ) {
x[i] = lower_bound ( a + , a + + len1, x[i] ) - a;
y[i] = lower_bound ( b + , b + + len2, y[i] ) - b;
mp[y[i]][x[i]] += w[i];
}
for ( int i = ; i <= n ; i++ )
for ( int j = ; j <= n ; j++ )
if ( mp[i][j] ) v[i].push_back ( j );
LL ans = ;
for ( int i = ; i <= n ; i++ ) {
for ( int j = ; j <= n ; j++ ) s[j] = mp[i][j];
build ( , n, );
ans = max ( ans, query ( , n, , , n ).maxx );
for ( int j = i + ; j <= n ; j++ ) {
for ( int k = ; k < v[j].size() ; k++ ) {
add ( , n, , v[j][k], mp[j][v[j][k]] );
}
ans = max ( ans, query ( , n, , , n ).maxx );
}
}
printf ( "%lld\n", ans );
}
return ;
}