Description

小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。

为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。

施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？

Input

第一行两个正整数N,M。

接下来M行，每行两个正整数Xi,Yi

Output

M行，第i行一个整数表示第i天过后小A能看到的楼房有多少栋

Sample Input

3 4

2 4

3 6

1 1000000000

1 1

Sample Output

1

1

1

2

数据约定

对于所有的数据1<=Xi<=N，1<=Yi<=109

N,M<=100000

HINT

Source

中国国家队清华集训 2012-2013 第一天

思路

对于一个建在i处高度为j的楼房，可以将它视为一条经过原点，斜率为ji，范围为[0,i]的直线，斜率存放在i点的数值上。那么对于一条直线y=kx,x∈[0,i]，如果满足对于每一个y=k1x,x∈[0,j]，[0,j]⊆[0,i]，并且k1<k，那么这条直线表示的楼房是可见的。

那么线段树上存两个数值：区间的斜率最大值，以及区间内可见的直线个数。前一个很好更新，那么后一个呢？显然可以用一些方法更新了。

分情况讨论：

1. 当右儿子的左儿子的区间最大值小于等于左儿子的区间最大值时，只统计右儿子的右儿子没有被遮挡的且大于左儿子的区间最大值即可。

2. 当右儿子的左儿子的区间最大值大于左儿子的区间最大值时，先统计右儿子的左儿子没有被遮挡且大于左儿子的区间最大值的个数，再统计右儿子的右区间没有被遮挡的值（右区间没有被遮挡的值总会大于左区间的最大值）。

代码

#include 
    
     #include 
     
      const int maxn=100000;struct segment_tree{  double maxv[(maxn<<2)+10];  int ans[(maxn<<2)+10];  int build(int now,int left,int right)  {    if(left==right)      {        ans[now]=0;        maxv[now]=0.0;        return 0;      }    int mid=(left+right)>>1;    build(now<<1,left,mid);    build(now<<1|1,mid+1,right);    maxv[now]=0.0;    ans[now]=0;    return 0;  }  int calc(int now,int left,int right,double cv)  //计算[left,right]这个区间内大于cv的值  {    if(maxv[now]<=cv)//这个区间没有统计价值了      {        return 0;      }    if(left==right)//已经到达最底端了      {        return 1;      }    int mid=(left+right)>>1;    if(maxv[now<<1]<=cv)//分情况讨论      {        return calc(now<<1|1,mid+1,right,cv);//对应上面的第1种情况      }    else      {        return calc(now<<1,left,mid,cv)+ans[now]-ans[now<<1];//对应上面的第2种情况      }  }  int change(int now,int left,int right,int pos,double cval)//将pos的值变为cval  {    if(left==right)//到达最低端可以更新了      {        maxv[now]=cval;        ans[now]=1;        return 0;      }    int mid=(left+right)>>1;    if(pos<=mid)      {        change(now<<1,left,mid,pos,cval);//更改左儿子      }    else      {        change(now<<1|1,mid+1,right,pos,cval);//更改右儿子      }    maxv[now]=std::max(maxv[now<<1],maxv[now<<1|1]);//更新max    ans[now]=ans[now<<1]+calc(now<<1|1,mid+1,right,maxv[now<<1]);//按上面的方法更新ans    return 0;  }};segment_tree st;int n,m,x,y;inline int read(){  int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {      if(ch=='-')        {          f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {      x=x*10+ch-'0';      ch=getchar();    }  return x*f;}int main(){  n=read();  m=read();  while(m--)    {      x=read();      y=read();      st.change(1,1,n,x,y/(double)x);      printf("%d\n",st.ans[1]);    }  return 0;}