总之就是找前面所有点的斜率都严格小于这个点的这样的点的个数

不管是询问还是修改都非常线段树啊，而且相当眼熟是不是和hotel有点像啊，大概就是区间内记一个len一个max，分别是当前区间答案和区间最大斜率，然后合并区间的时候用右区间递归，分情况讨论更新左区间

这样是两个log……

#include<iostream>

#include<cstdio>

using namespace std;

const int N=100005;

int n,m;

double a[N];

struct qwe

{

	int l,r,len;

	double mx;

}t[N<<2];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void build(int ro,int l,int r)

{

	t[ro].l=l,t[ro].r=r;

	if(l==r)

		return;

	int mid=(l+r)>>1;

	build(ro<<1,l,mid);

	build(ro<<1|1,mid+1,r);

}

int ques(int ro,double p)

{

	if(t[ro].l==t[ro].r)

		return p<t[ro].mx;

	int mid=(t[ro].l+t[ro].r)>>1;

	if(p>=t[ro<<1].mx)

		return ques(ro<<1|1,p);

	else

		return t[ro].len-t[ro<<1].len+ques(ro<<1,p);

}

void update(int ro,double p,int w)

{

	if(t[ro].l==t[ro].r)

	{

		t[ro].len=1,t[ro].mx=p;

		return;

	}

	int mid=(t[ro].l+t[ro].r)>>1;

	if(w<=mid)

		update(ro<<1,p,w);

	else

		update(ro<<1|1,p,w);

	t[ro].mx=max(t[ro<<1].mx,t[ro<<1|1].mx);

	t[ro].len=t[ro<<1].len+ques(ro<<1|1,t[ro<<1].mx);

}

int main()

{

	n=read(),m=read();

	if(n<=2000&&m<=2000)

	{

		while(m--)

		{

			int x=read(),y=read(),ans=0;

			a[x]=y;

			double mx=0;

			for(int i=1;i<=n;i++)

			{

				if(i>1&&mx<=1e9)

					mx=i*mx/(i-1);//cerr<<mx<<" ";

				if(a[i]>mx)

					ans++;

				mx=max(mx,a[i]);

			}//cerr<<endl;

			printf("%d\n",ans);

		}

		return 0;

	}

	build(1,1,n);

	while(m--)

	{

		double x=read(),y=read();

		update(1,y/x,(int)x);

		printf("%d\n",t[1].len);

	}

	return 0;

}