首页 > 代码库 > hdu5091 线段树
hdu5091 线段树
题意: 给了n个点在平面中 n<10000 然后 将这给了一个 宽为W 高为 H 的 矩形， 然后 使得这个矩形可以 涵盖最多的点有多少个，然后矩形的宽平行x 轴高平行y轴。可以将该矩形 水平或者上下移动，求他说能选中最多 多少个点，通过扫面线枚举每个x值的点 从小到大 ，选定区间后，将每个点的y值进行离散,然后以每个y为开始的点 分成 上下 的 区间 k个，然后建立一个 1到k 的 线段树， 对于每次选举的x 区间 操作这颗线段树， 因为我们知道 ， 对与 一个 y 他可能属于很多的区间， 这些区间是连续的，通过这个 我们可以用线段是的延迟更新解决这个问题。
#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>#include <vector>using namespace std;const int maxn = 10005;typedef int ll;struct point{ ll x,y; point(ll a=0, ll b=0){ x=a; y=b; }}P[maxn];ll cL,cR,value,N,H,W,ynum,xnum;struct Itree{ ll ma[maxn*4],se[maxn*4]; void build(ll o, ll L, ll R){ se[o]=ma[o]=0; if(L==R){ return ; } ll mid=(L+R)/2; build(o*2,L,mid); build(o*2+1,mid+1,R); } void matain(ll o){ ma[o]=max(ma[o*2]+se[o*2],ma[o*2+1]+se[o*2+1]); } void push(ll o){ se[o*2]+=se[o]; se[o*2+1]+=se[o]; se[o]=0; } void update( ll o, ll L, ll R){ if(cL<=L&&R<=cR){ se[o]+=value; return ; } ll mid =(L+R)/2; if(se[o]!=0){ push(o); } if(cL<=mid) update(o*2,L,mid); if(cR>mid) update(o*2+1,mid+1,R); matain(o); }}Q;vector<ll> F[maxn];ll X[maxn];ll Y[maxn];void solve(ll loc){ ll siz=F[loc].size(); for(ll i=0; i<siz; ++i){ ll y = F[loc][i]; cL = lower_bound(Y,Y+ynum,y-H)-Y+1; cR = lower_bound(Y,Y+ynum,y)-Y+1; Q.update(1,1,ynum); }}int main(){ while(scanf("%d",&N)==1){ if(N<0) break; scanf("%d%d",&W,&H); for(ll i=0; i<N; ++i){ scanf("%d%d",&X[i],&Y[i]); P[i]=point(X[i],Y[i]); } sort(X,X+N); xnum = unique(X,X+N)-X; for(ll i=0; i<=xnum; ++i) F[i].clear(); sort(Y,Y+N); ynum = unique(Y,Y+N)-Y; Q.build(1,1,ynum); for(ll i=0; i<N; ++i){ ll loc = lower_bound(X,X+xnum,P[i].x)-X; F[loc].push_back(P[i].y); } ll ans=0; for(ll i=0,j=0;j<xnum; ++j){ while(X[j]-X[i]>W) { value=-1; solve(i); i++; } value=1; solve(j); ans=max(ans,Q.ma[1]+Q.se[1]); } printf("%d\n",ans); } return 0;}
hdu5091 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。