http://acm.hdu.edu.cn/showproblem.php?pid=6638
先离散化坐标，枚举上下边界，线段树维护区间最大连续字段和。
1 #define bug(x) cout<<#x<<" is "<<x<<endl 2 #define IO std::ios::sync_with_stdio(0) 3 #include <bits/stdc++.h> 4 #define iter ::iterator 5 #define pa pair<int,ll> 6 using namespace std; 7 #define ll long long 8 #define mk make_pair 9 #define pb push_back 10 #define se second 11 #define fi first 12 #define rs o<<1|1 13 #define ls o<<1 14 ll mod=998244353; 15 const int N=2e3+5; 16 int T,n; 17 int X[N],Y[N]; 18 struct node{ 19 int x,y; 20 ll w; 21 }a[N]; 22 vector<pa>g[N]; 23 ll sum[N*4],L[N*4],R[N*4],mx[N*4]; 24 void push(int o){ 25 sum[o]=sum[ls]+sum[rs]; 26 L[o]=max(L[ls],sum[ls]+L[rs]); 27 R[o]=max(R[rs],sum[rs]+R[ls]); 28 ll t1=max(mx[ls],mx[rs]); 29 ll t2=max(t1,R[ls]+L[rs]); 30 mx[o]=0; 31 mx[o]=max(mx[o],t2); 32 } 33 void up(int o,int l,int r,int k,ll w){ 34 if(l==r){ 35 sum[o]+=w; 36 L[o]+=w; 37 R[o]+=w; 38 mx[o]+=w; 39 return; 40 } 41 int m=(l+r)/2; 42 if(k<=m)up(ls,l,m,k,w); 43 else up(rs,m+1,r,k,w); 44 push(o); 45 } 46 int main(){ 47 scanf("%d",&T); 48 while(T--){ 49 scanf("%d",&n); 50 for(int i=1;i<=n;i++){ 51 scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].w); 52 X[i]=a[i].x; 53 Y[i]=a[i].y; 54 } 55 sort(X+1,X+1+n); 56 sort(Y+1,Y+1+n); 57 58 int sz1=unique(X+1,X+1+n)-X-1; 59 int sz2=unique(Y+1,Y+1+n)-Y-1; 60 61 for(int i=1;i<=n;i++){ 62 a[i].x=lower_bound(X+1,X+1+sz1,a[i].x)-X; 63 a[i].y=lower_bound(Y+1,Y+1+sz2,a[i].y)-Y; 64 g[a[i].y].pb(mk(a[i].x,a[i].w)); 65 } 66 ll ans=0; 67 for(int i=1;i<=sz2;i++){ 68 for(int j=1;j<=sz1*4;j++){ 69 sum[j]=L[j]=R[j]=mx[j]=0; 70 } 71 for(int j=i;j>=1;j--){ 72 for(int k=0;k<g[j].size();k++){ 73 pa t=g[j][k]; 74 up(1,1,sz1,t.fi,t.se); 75 } 76 ans=max(ans,mx[1]); 77 } 78 } 79 printf("%lld ",ans); 80 for(int i=1;i<=sz2;i++)g[i].clear(); 81 } 82 }