BZOJ2957 楼房重建

题意

小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。
为了简化问题,我们考虑这些事件发生在一个二维平面上。小A在平面上$(0,0)$点的位置,第i栋楼房可以用一条连接$(i,0)$和$(i,H_i)$的线段表示,其中$H_i$为第$i$栋楼房的高度。如果这栋楼房上任何一个高度大于$0$的点与$(0,0)$的连线没有与之前的线段相交,那么这栋楼房就被认为是可见的。
施工队的建造总共进行了$M$天。初始时,所有楼房都还没有开始建造,它们的高度均为$0$。在第$i$天,建筑队将会将横坐标为$X_i$的房屋的高度变为$Y_i$(高度可以比原来大——修建,也可以比原来小——拆除,甚至可以保持不变——建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后,他能看到多少栋楼房?
$1 \leqslant n,m \leqslant 1e5$。

题解

考虑用线段树维护一个最大值,与只考虑这一个区间的答案。那么每次单点修改的时候,我们就要重新维护一下这个区间的答案。将修改点的右侧分为两个区间,若修改后楼房的高度,要比两个区间中的左区间要大,那么左区间对答案的贡献为$0$,继续递归计算右区间对答案的贡献,否则,右区间对答案的贡献不会改变,于是递归计算左区间即可。由于在push_up操作的复杂度为$O(logn)$,故总时间复杂度为$O(nlog^2n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=1e5+10;
int Ans[maxn<<2];
double Max[maxn<<2];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline int GetAns(int h,int l,int r,double Maxval){
if(l==r)return Max[h]>Maxval?1:0;
int mid=(l+r)>>1;
if(Maxval>Max[h<<1])return GetAns(h<<1|1,mid+1,r,Maxval);
else return Ans[h]-Ans[h<<1]+GetAns(h<<1,l,mid,Maxval);
}
inline void Modify(int h,int l,int r,int pos,double val){
if(l==r){
Max[h]=val;
Ans[h]=1;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)Modify(h<<1,l,mid,pos,val);
else Modify(h<<1|1,mid+1,r,pos,val);
Max[h]=max(Max[h<<1],Max[h<<1|1]);
Ans[h]=Ans[h<<1]+GetAns(h<<1|1,mid+1,r,Max[h<<1]);
}
int main(){
int i,j,k,m,n,q;
#ifndef ONLINE_JUDGE
freopen("BZOJ2957.in","r",stdin);
freopen("BZOJ2957.out","w",stdout);
#endif
n=read();q=read();
while(q--){
int x,y;
x=read();y=read();
Modify(1,1,n,x,y*1.0/x);
printf("%d\n",Ans[1]);
}
return 0;
}