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 100005 using 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; }

?

轉載于:https://www.cnblogs.com/Zars19/p/6964199.html

總結

以上是生活随笔為你收集整理的[BZOJ 2957]楼房重建（线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。