杭电2019多校第六场 HDU-6638 Snowy Smile （线段树+最大子矩阵和）

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6638

题意：T组样例。n个二维平面上的点，每个点有一个权值，问最大子矩阵和。

思路：

题解：首先将纵坐标离散化到 O(n) 的范围内，方便后续的处理。将所有点按照横坐标排序，枚举矩形的上边界，然后往后依次加入每个点，这样就确定了矩形的上下边界。设 v[y] 表示矩形内部纵坐标为 y 的点的权值和，则答案为 v 的最大子段和，用线段树维护带修改的最大子段和即可。时间复杂度 O(n 2 logn)。大致思路和题解一样，只不过枚举的是y的上下边界，维护的是x的最大子段和。

PS：这个题快烦死我了。数组开小了，杭电oj报TLE，调半天。在石油大oj上交又TLE，结果快读快写、手动离散化、二分、减少max的使用。哎。。。。。。。。什么时候oj能友好一点。。。。。。。。。。。

#include 
#define ll long long
#define gc get_char
#define cs const
using namespace std;
const int N = 2e3+10;
struct point
{int x,y,w;
}ps[N];
struct node
{int l,r;ll lmax,rmax,sum,maxx;
}tree[N<<2];
int bx[N],by[N],n,nx,ny;
bool cmpx(const point& a,const point& b)
{return a.x'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
}
inline void write(ll x)
{if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');
}
inline void build(int l,int r,int cur)
{tree[cur].l=l;tree[cur].r=r;tree[cur].lmax=tree[cur].rmax=tree[cur].sum=0;tree[cur].maxx=0;if(l==r)return ;int m=(l+r)>>1;build(l,m,cur<<1);build(m+1,r,cur<<1|1);return ;
}inline void pushup(int cur)
{tree[cur].maxx=max(max(tree[cur<<1].maxx,tree[cur<<1|1].maxx),tree[cur<<1].rmax+tree[cur<<1|1].lmax);tree[cur].lmax=max(tree[cur<<1].lmax,tree[cur<<1].sum+tree[cur<<1|1].lmax);tree[cur].rmax=max(tree[cur<<1|1].rmax,tree[cur<<1].rmax+tree[cur<<1|1].sum);tree[cur].sum=tree[cur<<1].sum+tree[cur<<1|1].sum;return ;
}inline void update(int tar,int cur,int val)
{if(tree[cur].l==tree[cur].r){tree[cur].lmax+=val;tree[cur].maxx=tree[cur].rmax=tree[cur].sum=tree[cur].lmax;		return ;}if(tar<=tree[cur<<1].r) update(tar,cur<<1,val);else update(tar,cur<<1|1,val);pushup(cur);return ;
}
inline int check(int y)
{int m,l=1,r=n,ans=0;while(l<=r){	m=(l+r)>>1;if(ps[m].y==y){if(m>ans) ans=m;l=m+1;	} else if(ps[m].ypre){pre=ps[i].x;ps[i].x=++nx;}else ps[i].x=nx;}sort(ps+1,ps+1+n,cmpy);pre=-2e9;for(int i=1;i<=n;i++){if(ps[i].y>pre){pre=ps[i].y;ps[i].y=++ny;}else ps[i].y=ny;}	ll ans=0;int upy;for(int i=1;i<=ny;i++){upy=check(i);build(1,nx,1);for(int down=i;down>=1;down--){while(upy&&ps[upy].y>=down){update(ps[upy].x,1,ps[upy].w);upy--;	}if(ans

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