[文章目录]
Description
小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的.施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大---修建，也可以比原来小---拆除，甚至可以保持不变---建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？N,M<=100000
线段树维护斜率。
将区间分开考虑：
假设区间前面挡了高为M的斜率。如果左儿子最大值小于M，那么只有右儿子对答案有贡献，对右儿子递归进行。反之，发现右儿子对区间的答案贡献不变，只需要统计左儿子的答案，可以递归进行。
总的区间答案就等于左儿子的答案+右儿子被左儿子最大斜率挡的答案。右儿子已经处理过了，可以logn完成合并。时间复杂度
线段树好可怕啊！！！
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 101000
using namespace std;
int n,m;
struct seg
{
int ans;
double mx;
}t[N<<2];
int getans(int pos,int l,int r,double dc)
{
if(l==r){return t[pos].mx>dc;}
int mid=l+r>>1;
if(t[pos<<1].mx<dc) return getans(pos<<1|1,mid+1,r,dc);
return t[pos].ans-t[pos<<1].ans+getans(pos<<1,l,mid,dc);
}
void fix(int pos,int l,int r,int x,double y)
{
if(l==r){t[pos].ans=1; t[pos].mx=y; return ;}
int mid=l+r>>1;
if(x<=mid) fix(pos<<1,l,mid,x,y);
else fix(pos<<1|1,mid+1,r,x,y);
t[pos].mx=max(t[pos<<1].mx,t[pos<<1|1].mx);
if(t[pos<<1].mx > t[pos<<1|1].mx) t[pos].mx=t[pos<<1].mx,t[pos].ans=t[pos<<1].ans;
else t[pos].mx=t[pos<<1|1].mx,t[pos].ans=t[pos<<1].ans+getans(pos<<1|1,mid+1,r,t[pos<<1].mx);
}
int main()
{
scanf("%d%d",&n,&m);
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
fix(1,1,n,x,1.0*y/x);
printf("%d\n",t[1].ans);
}
return 0;
}