Description

　　小A的樓房外有一大片施工工地，工地上有N棟待建的樓房。每天，這片工地上的房子拆了又建、建了又拆。他經常無聊地看著窗外發呆，數自己能夠看到多少棟房子。
　　為了簡化問題，我們考慮這些事件發生在一個二維平面上。小A在平面上(0,0)點的位置，第i棟樓房可以用一條連接(i,0)和(i,Hi)的線段表示，其中Hi為第i棟樓房的高度。如果這棟樓房上任何一個高度大于0的點與(0,0)的連線沒有與之前的線段相交，那么這棟樓房就被認為是可見的。
　　施工隊的建造總共進行了M天。初始時，所有樓房都還沒有開始建造，它們的高度均為0。在第i天，建筑隊將會將橫坐標為Xi的房屋的高度變為Yi(高度可以比原來大—修建，也可以比原來小—拆除，甚至可以保持不變—建筑隊這天什么事也沒做)。請你幫小A數數每天在建筑隊完工之后，他能看到多少棟樓房？

Input

　　第一行兩個正整數N,M
　　接下來M行，每行兩個正整數Xi,Yi

Output

　　M行，第i行一個整數表示第i天過后小A能看到的樓房有多少棟

Sample Input

3 4

2 4

3 6

1 1000000000

1 1

Sample Output

1

1

1

2

數據約定

　　對于所有的數據1<=Xi<=N，1<=Yi<=10^9

N,M<=100000

Solution

• 可以看到的高度都是單調上升的，修改一個值只會影響后面的答案。

• 于是我們可以用線段樹維護單調棧（斜率從小到大）。

• 線段樹上維護兩個值：最大值 F 和 單調棧大小（即答案）G 。

• 對于線段樹上的某一點（對應著一條線段），當前修改的值為 qy 。有以下兩種情況：

• ①：若 F≤qy ，說明當前線段中的值在單調棧中會被全部彈完，則貢獻為 0 ，不用處理。

• ②：若 F>qy ，則將當前線段分為兩段（左子樹和右子樹），

• 若左側的 F 值 ≤qy ，則左側貢獻為 0 ，只需遞歸右子樹統計答案即可（同情況①）。

• 否則呢左側答案不會影響右側，右側答案不變并只需遞歸左子樹即可。

• 過程中不斷維護 G 值，詢問時輸出 G[1] （即整個線段的答案）即可。

• 聽說時間復雜度為 O(N?log2N) 。

Code

#include<cstdio> #include<cctype> using namespace std; const int N=1e5+5; int qx; double qy; double f[N<<2]; int g[N<<2]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } int get(int v,int l,int r,double val) {if(l==r) return f[v]>val;int mid=l+r>>1;if(f[v<<1]<=val) return get(v<<1|1,mid+1,r,val);return get(v<<1,l,mid,val)+g[v]-g[v<<1]; } void change(int v,int l,int r) {if(l==r){f[v]=qy;g[v]=1;return;}int mid=l+r>>1;if(qx<=mid) change(v<<1,l,mid); else change(v<<1|1,mid+1,r);f[v]=f[v<<1]>f[v<<1|1]?f[v<<1]:f[v<<1|1];g[v]=g[v<<1]+get(v<<1|1,mid+1,r,f[v<<1]); } int main() {int n=read(),m=read();while(m--){qx=read(),qy=read()*1.0/qx;change(1,1,n);write(g[1]),putchar('\n');}return 0; }

總結

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

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