首页 > 代码库 > [BZOJ 2957]楼房重建（线段树）
[BZOJ 2957]楼房重建（线段树）
Description
小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大---修建，也可以比原来小---拆除，甚至可以保持不变---建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？
Solution
把每栋楼房高度角的tan值放在线段树上维护，然后就变成了一个动态求最长上升子序列的问题
于是线段树每个节点都维护max和ans，这个ans可以由左子树的ans+右子树中大于左边max的最长上升子序列得到，后面的这一部分可以在右子树进行二分
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#define MAXN 100005using namespace std;int n,m;int read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}struct Node{ int l,r,ans; double maxn;}t[MAXN*4];void build(int idx,int l,int r){ t[idx].l=l,t[idx].r=r,t[idx].maxn=t[idx].ans=0; if(l==r)return; int mid=(l+r)>>1; build(idx<<1,l,mid),build(idx<<1|1,mid+1,r);}int update(int idx,double v){ if(t[idx].l==t[idx].r)return t[idx].maxn>v; if(t[idx<<1].maxn<=v)return update(idx<<1|1,v); return t[idx].ans-t[idx<<1].ans+update(idx<<1,v);}void add(int idx,int p,double x){ if(t[idx].l==t[idx].r){t[idx].maxn=x;t[idx].ans=1;return;} int mid=(t[idx].l+t[idx].r)>>1; if(p<=mid)add(idx<<1,p,x);else add(idx<<1|1,p,x); t[idx].maxn=max(t[idx<<1].maxn,t[idx<<1|1].maxn); t[idx].ans=t[idx<<1].ans+update(idx<<1|1,t[idx<<1].maxn);}int main(){ n=read(),m=read(); build(1,1,n); for(int i=1;i<=m;i++) { int x=read(),y=read(); add(1,x,(double)y/x); printf("%d\n",t[1].ans); } return 0;}
[BZOJ 2957]楼房重建（线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。