大致题意： 有(n)个楼房，第(i)个楼房可以表示为连结((i,0))和((i,H_i))的线段，且第(i)个楼房可以被看见当且仅当连结((0,0))和((i,H_i))的线段与表示其他楼房的线段无交点。每次单点修改(H_i)，求每次修改后能看到几个楼房。
前言
(Jan 29th)刷题计划（6/6），算法标签：线段树。
终于完成了今天的计划了！
斜率
令楼房(_i)表示连结((i,0))和((i,H_i))的线段，视线(_i)表示连结((0,0))和((i,H_i))的线段。
考虑视线(_i)与楼房(_{1sim i-1})无交点，就是视线(_i)的斜率大于视线(_{1sim i-1})的斜率。而此处的斜率，即为(frac {H_i}i)。
也就是说，题目要求的就是视线斜率的上升子序列的长度（注意，不是最长上升子序列）。
线段树
考虑用线段树进行维护。
对于线段树上每一个点，我们维护两个信息：这个点所代表的区间的最大值(Mx)和上升子序列的长度(f)。则显然每次的答案就是根节点的(f)。
(Mx)的维护就是常规操作，而(f)的维护就比较有技巧了。
我们可以新定义一个函数(Calc(x,l,r,rt))，代表在([l,r])这个区间里大于(x)的上升序列长度，则：
[f(rt)=f(lc)+Calc(Mx(lc),mid+1,r,rc)
]
[Calc(x,l,r,rt)=egin{cases}f(rt)&l=r且x<Mx(rt)\0&l=r且xge Mx(rt)\Calc(x,l,mid,lc)+f(rt)-f(lc)&l≠r且x<Mx(lc)\Calc(x,mid+1,r,rc)&l≠r且xge Mx(lc)end{cases}
]
这样我们就可以在(O(logN))的时间复杂度内实现(PushUp())，因而总复杂度是(O(Nlog^2N))的。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define DB double
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
int n,m;
class SegmentTree
{
private:
#define PT CI l=1,CI r=n,CI rt=1
#define LT l,mid,rt<<1
#define RT mid+1,r,rt<<1|1
#define PU(x) (O[x]=node(O[x<<1].f+Calc(O[x<<1].Mx,RT),max(O[x<<1].Mx,O[x<<1|1].Mx)))//注意上升子序列长度的上传
struct node {int f;DB Mx;I node(CI p=0,Con DB& t=0):f(p),Mx(t){}}O[N<<2];
public:
I void Upt(CI x,Con DB& y,PT)//单点修改
{
if(l==r) return (void)(O[rt]=node(1,y));int mid=l+r>>1;
x<=mid?Upt(x,y,LT):Upt(x,y,RT),PU(rt);
}
I int Calc(Con DB& x,PT)//求出区间内大于x的上升序列的长度
{
if(l==r) return x<O[rt].Mx?O[rt].f:0;int mid=l+r>>1;//特判边界
return x<O[rt<<1].Mx?Calc(x,LT)+O[rt].f-O[rt<<1].f:Calc(x,RT);//递归求解
}
I int Qry() {return O[1].f;}//整个序列的答案
}S;
int main()
{
RI i,x,y;for(scanf("%d%d",&n,&m),i=1;i<=m;++i)
scanf("%d%d",&x,&y),S.Upt(x,1.0*y/x),printf("%d
",S.Qry());//线段树上存储斜率
return 0;
}