一眼数据结构。
考虑线段树，记录该区间能看到最多的建筑数量 \(ans_{wz}\) 以及看到区间中最大的斜率（或者说，该区间内最后看到的建筑）\(xl_{wz}\)。
很明显，假如我现在的修改操作是 \((x,y)\)，那么会改变 \(\log_n\) 个节点，即包含 \(x\) 的节点，考虑如何修改他们的 \(ans\) 和 \(xl\)。
对于叶子节点，\(ans_{wz}=1,xl_{wz}=\frac{y}{x}\)
对于其他的节点，就是左儿子的答案 \(+\) 右儿子答案中大于左儿子斜率的建筑数量（因为先看到前面的建筑再看到后面的建筑），不妨设此时左儿子最大斜率为 \(xl_{zuo}\)。
很难 \(O(1)\) 求出来，所以考虑 \(O(\log_n)\) 的时间复杂度内求出。
递归找右儿子中大于左儿子斜率的数量，不妨设我们递归到 \([l,r]\) 这个区间。
考虑 \([l,mid]\) 这个区间的最大斜率
\(1\)、这个最大斜率小于等于 \(xl_{zuo}\)，那么直接递归右儿子，即 \([mid+1,r]\) 这个区间
\(2\)、这个最大斜率大于 \(xl_{zuo}\)，那么递归左儿子，返回的答案加上\(ans_{[l,r]}-ans_{[l,mid]}\)（这个区间没有受到 \((x,y)\) 的影响，所以这个差就是比该区间内右儿子答案大于左儿子斜率的建筑数量）。
最后的时间复杂度就是 \(O(n \log^2 n)\)
上代码：
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const ll N=1e5+50;
ll n,m,ans[N*4];
db xl[N*4];
ll query(ll wz,ll l,ll r,db x)
{
if(xl[wz]<=x) return 0;
if(l==r) return (xl[wz]>x);
ll mid=(l+r)/2;
if(xl[wz*2]<=x) return query(wz*2+1,mid+1,r,x);
return query(wz*2,l,mid,x)+ans[wz]-ans[wz*2];
}
void change(ll wz,ll l,ll r,ll md,db x)
{
if(l==r)
{
ans[wz]=1;
xl[wz]=x;
return ;
}
ll mid=(l+r)/2;
if(md<=mid) change(wz*2,l,mid,md,x);
else change(wz*2+1,mid+1,r,md,x);
xl[wz]=max(xl[wz*2],xl[wz*2+1]);
ans[wz]=ans[wz*2]+query(wz*2+1,mid+1,r,xl[wz*2]);
}
int main()
{
scanf("%lld %lld",&n,&m);
for(ll i=1,x,y;i<=m;i++)
{
scanf("%lld %lld",&x,&y);
change(1,1,n,x,(db)y/x);
printf("%lld\n",ans[1]);
}
return 0;
}