bzoj2957 楼房重建

题意

一个平面开始时为空,$x$坐标的范围是$[1,n]$,有$m$次操作每次改变一个横坐标上的线段的高度,问从$(0,0)$点能看到多少线段(如果一个线段被前面的线段挡住了,那么看不到)。

分析

维护一个线段树,每个区间里记录这个区间的最大斜率和只考虑这个区间时,能看到的线段条数。

由子节点更新父结点时,子节点$lson$的答案肯定是不变的,但是$rson$的答案会改变,因为$lson$里会有线段遮住右儿子的线段,所以只需要重新计算右儿子的答案再加回来即可。计算一个区间的比$val$大的数有几个时,分为两种情况,一种是$maxv[lson] \le val$,此时左儿子没有贡献,递归去计算右儿子的值即可;另一种是$maxv[lson]>val$,那么此时右儿子的答案不会改变,因为右儿子无论如何一定建立在左儿子最大的基础上,所以重新计算左儿子的答案,再加上右儿子本身的答案即可。

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 <bits/stdc++.h>
using namespace std;
const int maxn=(int)1e5+5;
double maxv[maxn<<2];
int ans[maxn<<2];
inline int readInt()
{
char c=0;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
int n,m;
#define lson (o<<1)
#define rson (o<<1|1)
int Count(int o,int l,int r,double UP)
{
if(l>r) return 0;
if(l==r) return maxv[o]>UP;
else{
int mid=(l+r)>>1;
if(UP>=maxv[lson]) return Count(rson,mid+1,r,UP);
else return ans[o]-ans[lson]+Count(lson,l,mid,UP);
}
}
void Upos(int o,int l,int r,int pos,double val)
{
if(pos>r || pos<l) return;
if(l==r && pos==l) {maxv[o]=val,ans[o]=1;return;}
else {
int mid=(l+r)>>1;
if(pos<=mid) Upos(lson,l,mid,pos,val);
else Upos(rson,mid+1,r,pos,val);
maxv[o]=max(maxv[lson],maxv[rson]);
ans[o]=ans[lson]+Count(rson,mid+1,r,maxv[lson]);
}
}
int main()
{
int x,y;
n=readInt(),m=readInt();
for(int i=1;i<=m;i++){
x=readInt(),y=readInt();
Upos(1,1,n,x,(double)y/x);
printf("%d\n",ans[1]);
}
return 0;
}