思路：
记录每栋楼楼顶与原点连线的斜率 那么一栋楼可见当且仅当前面所有楼的斜率都小于这栋楼
将n栋楼分为√(0.5*n*logn)块 每一块内维护一个单调上升子序列(注意不是LCS) 比如说4 1 2 3 5 那么维护的序列就是4 5
修改的时候块内暴力重建 然后查询顺着块撸一遍 每次记录当前的最大值 然后去下一个块中二分找到第一个比这个最大值大的值 然后统计答案&&更新最大值
from popoqqq
//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100050,Block=500;
int n,m,block[N],rec[N],xx,yy;
double a[N],stk[222][555];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=100000;i++)block[i]=(i-1)/Block+1;
while(m--){
scanf("%d%d",&xx,&yy);
double temp=1.0*yy/xx,now=0;
a[xx]=temp,rec[block[xx]]=0;
for(int i=lower_bound(block+1,block+100001,block[xx])-block;block[i]==block[xx];i++)
if(a[i]>now)now=a[i],stk[block[xx]][++rec[block[xx]]]=a[i];
int ans=0,T;now=0;
for(int i=1;i<=block[n];i++){
int l=0,r=rec[i];
while(l<=r){
int mid=(l+r)>>1;
if(stk[i][mid]<=now)l=mid+1;
else r=mid-1;
}
ans+=rec[i]-l+1,now=max(stk[i][rec[i]],now);
}
printf("%d
",ans);
}
}