Snowy Smile（线段树维护最大字段 最大子矩阵）

原题： http://acm.hdu.edu.cn/showproblem.php?pid=6638

题意：

给出$[-1e9,1e9]$上的$2e3$个点，求最大子矩阵。

解析：

一般的 O ( N 3 ) O(N^3) O(N3)的做法不能做了，考虑这个题的特点，虽然离散化后有$2e3$种横坐标，$2e3$种纵坐标，如果做$4e6$个点的方法一定是不行了。

我们用$3e3$个点的角度去考虑，先枚举上下边界，下边界往下延的过程中用线段树维护区间最大子段。

时间复杂度 O ( N 2 l o g N ) O(N^2log_N) O(N2logN​)

代码：

#include
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
const int maxn=2009;int n;
struct Node {LL Sum,Max,Lmax,Rmax;
} Tr[maxn<<2];struct Uni {int num;LL tmp[maxn];void init() {sort(tmp+1,tmp+1+num);num=unique(tmp+1,tmp+1+num)-tmp-1;}void transform(LL &val) {val=lower_bound(tmp+1,tmp+1+num,val)-tmp;}
} Ux,Uy;void PushUp(Node &Ans,Node Lef,Node Rig) {Ans.Sum=Lef.Sum+Rig.Sum;Ans.Max=max(max(Lef.Max,Rig.Max),Lef.Rmax+Rig.Lmax);Ans.Lmax=max(Lef.Lmax,Lef.Sum+Rig.Lmax);Ans.Rmax=max(Rig.Rmax,Rig.Sum+Lef.Rmax);
}void Build(int rt=1,int l=1,int r=Uy.num) {Tr[rt].Sum=Tr[rt].Max=Tr[rt].Lmax=Tr[rt].Rmax=0;if(l==r) {return;}Build(ls,l,mid);Build(rs,mid+1,r);
}void Update(int pos,LL val,int rt=1,int l=1,int r=Uy.num) {if(l==r) {Tr[rt].Sum=Tr[rt].Max=Tr[rt].Lmax=Tr[rt].Rmax=Tr[rt].Sum+val;return;}if(pos<=mid)Update(pos,val,ls,l,mid);elseUpdate(pos,val,rs,mid+1,r);PushUp(Tr[rt],Tr[ls],Tr[rs]);
}Node Query(int L=1,int R=Uy.num,int rt=1,int l=1,int r=Uy.num) {if(l>=L&&r<=R) {return Tr[rt];}if(R<=mid)return Query(L,R,ls,l,mid);if(L>mid)return Query(L,R,rs,mid+1,r);Node Ans,Lef=Query(L,R,ls,l,mid),Rig=Query(L,R,rs,mid+1,r);PushUp(Ans,Lef,Rig);return Ans;
}struct Point {LL x,y,val;bool operator<(const Point &R)const{return x<R.x;}
} e[maxn];int main() {int _;for(scanf("%d",&_); _--;) {scanf("%d",&n);rep(i,1,n) {scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].val);Ux.tmp[i]=e[i].x;Uy.tmp[i]=e[i].y;}Ux.num=Uy.num=n;Ux.init();Uy.init();rep(i,1,n) {Ux.transform(e[i].x);Uy.transform(e[i].y);}sort(e+1,e+1+n);LL ans=0;rep(i,1,Ux.num){Build();int At=1;while(e[At].x<i)At++;rep(j,i,Ux.num){while(At<=n&&e[At].x==j)Update(e[At].y,e[At].val),++At;ans=max(ans,Query().Max);}}printf("%lld\n",ans);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！