题意：有n个点（n<=2000），每个点都有价值，求一个矩形内所有点价值和的最大值是多少
一维的静态最大子段和用dp在O(n)时间内解决，带修改查询区间最大子段和可以用线段树区间合并O(nlogn)写
二维的最大子矩阵和可以通过压行再dpO(n^3)写。
这题对坐标离散化一下就转化为求最大子矩阵和的问题了，然后n^3肯定是不行的，然后利用离散后是2000*2000的图上有2000个点，矩阵很稀疏这个性质，可以通过枚举起始行s，终点行e，用然后用线段树维护s~e行，每列的信息，转化为一维最大子段和来算。每次枚举起始行时都要重新建树，然后枚举终点行时，都把这行的信息更新到线段树里去，复杂度是n(nlogn(建树)+nlogn（更新）)，这题关键是有效点很少只有n个，如果是n^2个就没了。
#include<bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs (rt<<1)+1
#define ll long long
#define fuck(x) cout<<#x<<" "<<x<<endl;
typedef pair<int,int>pii;
const ll inf=9e18;
const int maxn=2000+10;
int d[4][2]={1,0,-1,0,0,1,0,-1};
vector<pii>row[maxn];
struct node{
int x,y,w;
}p[maxn];
int lshx[maxn],lshy[maxn],cnt1,cnt2;
ll maxx[maxn<<2],lmaxx[maxn<<2],rmaxx[maxn<<2],sum[maxn<<2];
void pushup(int rt)
{
sum[rt]=sum[ls]+sum[rs];
lmaxx[rt]=max(lmaxx[ls],sum[ls]+lmaxx[rs]);
rmaxx[rt]=max(rmaxx[rs],sum[rs]+rmaxx[ls]);
maxx[rt]=max(maxx[ls],maxx[rs]);
maxx[rt]=max(maxx[rt],rmaxx[ls]+lmaxx[rs]);
}
void update(int rt,int L,int R,int pos,int val){
if(L==R)
{
sum[rt]+=val;
maxx[rt]=lmaxx[rt]=rmaxx[rt]=max(0LL,sum[rt]);
return ;
}
int mid=(L+R)>>1;
if(pos<=mid)
update(ls,L,mid,pos,val);
else
update(rs,mid+1,R,pos,val);
pushup(rt);
}
int main(){
int t,n;
ll ans;
scanf("%d",&t);
while(t--)
{
ans=-inf;
cnt1=cnt2=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) row[i].clear();
for(int i=1;i<=n;i++) scanf("%d%d%d",&(p[i].x),&(p[i].y),&(p[i].w)),lshx[++cnt1]=p[i].x,lshy[++cnt2]=p[i].y;
sort(lshx+1,lshx+cnt1+1);
sort(lshy+1,lshy+cnt2+1);
cnt1=unique(lshx+1,lshx+cnt1+1)-lshx-1;
cnt2=unique(lshy+1,lshy+cnt2+1)-lshy-1;
for(int i=1;i<=n;i++)
{
int tmpx,tmpy;
tmpx=lower_bound(lshx+1,lshx+cnt1+1,p[i].x)-lshx;
tmpy=lower_bound(lshy+1,lshy+cnt2+1,p[i].y)-lshy;
row[tmpx].push_back(make_pair(tmpy,p[i].w));
}
for(int i=1;i<=cnt1;i++)
{
for(int j=1;j<=cnt2*4;j++)
maxx[j]=lmaxx[j]=rmaxx[j]=sum[j]=0;
for(int j=i;j<=cnt1;j++)
{
for(int k=0;k<row[j].size();k++)
update(1,1,cnt2,row[j][k].first,row[j][k].second);
ans=max(ans,maxx[1]);
}
}
printf("%lld
",ans);
}
return 0;
}