在杜教直播中得知2018多校第八场第10题和这个题很相近，所以先补这个题。

代码和思路借鉴了这篇博客：http://hzwer.com/6746.html。

这题是询问从原点能看到的楼房数目,首先对某一个点修改后，对之前的点没有影响，所以只需要处理后面的点，而后面的点分为两种情况：

1：查询区间的左半部分的最大值小于等于修改的值，这种情况不用管左半区间了，因为左半区间对答案更新没有影响，更新右半区间就行了。

2：左半区间的最大值大于修改的值，那么只用更新左半区间的值就行了，不影响右侧的贡献（右侧的贡献取决于左侧的最大值）。

代码：

#include
     
      using namespace std;const int maxn=100010;struct node{	int l,r,cnt;	double val;}t[4*maxn];void build(int o,int l,int r){	t[o].l=l,t[o].r=r;	int mid=(l+r)>>1;	if(l==r)return;	build(o<<1,l,mid);	build(o<<1|1,mid+1,r);}int cal(int o,double val){	int l=t[o].l,r=t[o].r;	if(l==r)return t[o].val>val;	if(t[o<<1].val<=val)return cal(o<<1|1,val);	return t[o].cnt-t[o<<1].cnt+cal(o<<1,val);}void update(int o,int pos,double val){	int l=t[o].l,r=t[o].r,mid=(l+r)>>1;	if(l==r){		t[o].cnt=1;		t[o].val=val;		return;	}	if(pos<=mid)update(o<<1,pos,val);	else update(o<<1|1,pos,val);	t[o].val=max(t[o<<1].val,t[o<<1|1].val);	t[o].cnt=t[o<<1].cnt+cal(o<<1|1,t[o<<1].val);}int main(){	int n,m,x,y;	scanf("%d%d",&n,&m);	build(1,1,n);	while(m--){		scanf("%d%d",&x,&y);		update(1,x,(double)y/x);		printf("%d\n",t[1].cnt);	}}