题意分析
设第 $i$ 栋楼房的高度为 $h_i$。
那么 $(i,h_i)$ 能被看见当且仅当：
\[\max_{j=1}^{i-1}\dfrac{h_j}j<\dfrac{h_i}{i}\]记 $k_i=\dfrac{h_i}i$，则题意即动态维护一个序列，$k_1$ 必须选，且选中的 $k_i$ 均为前缀严格最大值。
普通静态方法都不行，不能接受。考虑充分利用已有信息，那么容易想到线段树合并区间。
对于节点 $p$，维护 $\textit{len}_p$ 表示 $[l_p,r_p]$ 的最长长度。
考虑 $[l,\textit{mid}],[\textit{mid}+1,r]$ 合并到 $[l,r]$。
显然 $[l,\textit{mid}]$ 部分的答案一定不变，重要的是如何求出 $[\textit{mid}+1,r]$ 的答案。右子区间 $[\textit{mid}+1,r]$ 内最终选中的所有 $k_i$ 必须都要大于左子区间 $[l,\textit{mid}]$ 的最大值，记为 $s=\max[l,\textit{mid}]$。
对于 $[\textit{mid}+1,r]$ 内，设其左子区间 $[l’,\textit{mid}’]$、右子区间 $[\textit{mid}’+1,r’]$。
-
若 $\max[l’,\textit{mid}’]\leq s$，则 $[l’,\textit{mid}’]$ 一定不在答案内，答案在 $[\textit{mid}’+1,r]$ 中。
-
若 $\max[l’,\textit{mid}’]>s$，则 $[l’,\textit{mid}’]$ 一定在答案内，需要先计算这一部分。
考虑 $[\textit{mid}’+1,r’]$ 的答案是什么，和上面是类似的，这一部分要大于 $\max[l’,\textit{mid}’+1]$。
因此直接得到这一部分的答案为 $\textit{len}{[l’,r’]}-\textit{len}{[l’,\textit{mid}’]}$。
由于线段树的性质，处理 $[l,r]$ 时，这些信息都已知。
这么看下来，这就是一个递归求解的过程，单次复杂度 $\mathcal O(\log n)$。
形式化地，设 $\operatorname{find}(p,s)$ 表示 $[l_p,r_p]$ 内大于 $s$ 的答案（不一定从 $l_p$ 开始），$\textit{lChild}_p,\textit{rChild}_p$ 分别为左右子节点，$\textit{max}_p$ 表示 $[l_p,r_p]$ 内的最大值。
则：
\[\operatorname{find}(p,s)= \begin{cases} 0&\textit{max}_p\leq s\\ 1&l_p=r_p\\ \operatorname{find}(\textit{rChild}_p,s)&\textit{max}_{\textit{lChild}_p}\leq s\\ \operatorname{find}(\textit{lChild}_p,s)+\textit{len}_p-\textit{len}_{\textit{lChild}_p}&\text{otherwise.} \end{cases}\]总时间复杂度 $\mathcal O\left(m\log^2n\right)$。
AC 代码
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1e5;
struct k{
int x,y;
k(){
x=1,y=-2147483647;
}
k(int x2,int y2){
x=x2,y=y2;
}
};
bool operator <(k a,k b){
return 1ll*a.y*b.x < 1ll*b.y*a.x;
}
bool operator >(k a,k b){
return 1ll*a.y*b.x > 1ll*b.y*a.x;
}
bool operator ==(k a,k b){
return 1ll*a.y*b.x == 1ll*b.y*a.x;
}
bool operator <=(k a,k b){
return !(a>b);
}
struct segTree{
struct node{
int l,r,len;
k max;
}t[N<<2|1];
int find(int p,k s){
if(t[p].max<=s){
return 0;
}else if(t[p].l==t[p].r){
return 1;
}else if(t[p<<1].max<=s){
return find(p<<1|1,s);
}else{
return find(p<<1,s)+t[p].len-t[p<<1].len;
}
}
void up(int p){
t[p].max=max(t[p<<1].max,t[p<<1|1].max);
t[p].len=t[p<<1].len+find(p<<1|1,t[p<<1].max);
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r){
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(p);
}
void set(int p,int x,int y){
if(t[p].l==t[p].r){
t[p].max={x,y};
t[p].len=1;
return;
}
if(x<=t[p<<1].r){
set(p<<1,x,y);
}
if(t[p<<1|1].l<=x){
set(p<<1|1,x,y);
}
up(p);
}
int query(){
return t[1].len;
}
}t;
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
t.build(1,1,n);
while(m--){
int x,y;
cin>>x>>y;
t.set(1,x,y);
cout<<t.query()<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
