题面

　　小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
　　为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上$(0,0)$点的位置，第i栋楼房可以用一条连接$(i,0)$和$(i,Hi)$的线段表示，其中$Hi$为第$i$栋楼房的高度。如果这栋楼房上任何一个高度大于$0$的点与$(0,0)$的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
　　施工队的建造总共进行了$M$天。初始时，所有楼房都还没有开始建造，它们的高度均为$0$。在第i天，建筑队将会将横坐标为$X_i$的房屋的高度变为$Y_i$(高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？

思路

一看到这题就很自然的想到斜率，其实这题的本质就是让我们维护斜率单调上升的序列，并且是唯一的，从最左边开始的单调上升序列。为什么，来看一张图。

那么这道题就被化简为了带单点修改的询问全局单调上升序列长度。咋做呢，说实在的，不大好想。我们维护一个区间最大，区间单调上升序列长度(答案)，还有一个函数$find(root,v)$，表示在$root$维护的区间开头放一个$v$能构成的上升序列长度,假设我们有一个区间，我们考虑如何用他的左右区间合并得到他的答案，首先最大值不用说了。我们有一个很显然的结论就是左区间的上升序列长度肯定要合并上去，然后考虑右区间，如果把左区间的最大值作为$v$，右区间的$root$作为$root$，那么如果v大于右区间的左区间的最大值，那么左区间的上升序列长度一定没有用了，只要考虑右区间。如果v小于等于右区间的左区间的最大值，那么需要更新左区间的上升序列长度，用右区间的上升序列长度-右区间的左区间的上升序列长度+find(右区间的左区间root，原来的v)即可更新。

代码

#include<bits/stdc++.h>
using namespace std;
int N,M,root,id=0;
struct seg{double Max;int tot,ls,rs;}tree[100005*40];
inline int find(int root,int l,int r,double v)
{
	if (l==r) return v<tree[root].Max;
	int mid=l+r>>1;
	if (tree[tree[root].ls].Max<v) return find(tree[root].rs,mid+1,r,v);
	else return tree[root].tot-tree[tree[root].ls].tot+find(tree[root].ls,l,mid,v);
}
inline void build(int &root,int l,int r)
{
	if (!root) root=++id;
	tree[root].tot=0;tree[root].Max=0;
	if (l==r) return;
	int mid=l+r>>1;
	build(tree[root].ls,l,mid),build(tree[root].rs,mid+1,r);
}
inline void update(int root,int l,int r,int wz,double num)
{
	if (l==r) {tree[root].Max=num;tree[root].tot=1;return;}
	int mid=l+r>>1;
	if (wz<=mid) update(tree[root].ls,l,mid,wz,num);else update(tree[root].rs,mid+1,r,wz,num);
	tree[root].Max=max(tree[tree[root].ls].Max,tree[tree[root].rs].Max);
	tree[root].tot=tree[tree[root].ls].tot+find(tree[root].rs,mid+1,r,tree[tree[root].ls].Max);
}
int main()
{
	scanf("%d%d",&N,&M);
	build(root,1,N);
	for (int i=1;i<=M;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		update(root,1,N,x,(double)y/x);
		cout<<find(root,1,N,0)<<endl;
	}
	return 0;
}