线段树

计算楼顶和 $(0,0)$ 连线的线段斜率，如果一条线段的斜率比它左边所有线段的斜率都大，这条线段对应的楼就可见。

使用线段树维护序列前缀最大值取值的数量，需要用到一些技巧，这样的线段树也被称为陈亮舟线段树。

对节点维护区间最大值和区间前缀最大值取值数，考虑如何合并子节点信息，直接继承左儿子的信息（左儿子对应的区间前面的区间对左儿子造成的影响会在后续合并中计算），由于左儿子的区间最大值可能比右儿子贡献给区间前缀最大值取值数中的一部分取值更大或相等，需要计算右儿子比左儿子区间最大值更大的前缀最大值取值数。

使用函数 int query(int u,double k) 来计算节点 $u$ 在给定限制 $k$ 下的前缀最大值取值数，时间复杂度 $O(\log n)$。

constexpr double eps=1e-14;//开 1e-9 或者更大会 WA 掉
//本题中有楼房的位置的权值为 1 其余位置权值为 0
struct Segment{
    int l,r,w;//区间 [l,r] 中所有位置的权值和为 w
    double k;//区间 [l,r] 斜率最大值
}s[400'005];
int query(int u,double k){
    if(s[u].l==s[u].r) return (s[u].k>k)*s[u].w;//计入当前位置贡献
    if(s[u*2].k-k<eps) return query(u*2+1,k);//左子树无贡献
    //上面的判断条件等价于 s[u*2].k<=k 为了规避浮点误差使用 eps 判断
    return s[u].w-s[u*2].w+query(u*2,k);//左子树存在比 k 更大的数
    //继承右子树对当前节点的贡献 注意是 query(u*2+1,s[u*2].k) 的值而不是 s[u*2+1].w 的值
}

单点修改的时间复杂度为 $O(\log^2 n)$，由于 $n,m$ 同阶，总体时间复杂度 $O(n \log^2 n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr double eps=1e-14;
struct Segment{int l,r,w;double k;}s[400'005];
int n,m;
void build(int u,int l,int r){
    s[u].l=l,s[u].r=r;
    if(l==r) return;
    build(u*2,l,(l+r)/2);
    build(u*2+1,(l+r)/2+1,r);
}
int query(int u,double k){
    if(s[u].l==s[u].r) return (s[u].k>k)*s[u].w;
    if(s[u*2].k-k<eps) return query(u*2+1,k);
    return s[u].w-s[u*2].w+query(u*2,k);
}
void update(int u,int p,double k){
    if(s[u].l==s[u].r) return s[u].w=1,s[u].k=k,void();
    if(p<=s[u*2].r) update(u*2,p,k);
    else update(u*2+1,p,k);
    s[u].w=s[u*2].w+query(u*2+1,s[u*2].k);
    s[u].k=max(s[u*2].k,s[u*2+1].k);
}
int main(){
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        static int x,y;
        scanf("%d%d",&x,&y);
        update(1,x,1.0*y/x);
        printf("%d\n",s[1].w);
    }
    return 0;
}