来自FallDream的博客，未经允许，请勿转载，谢谢。
小A的楼房外有一大片施工工地，工地上有N栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)点的位置，第i栋楼房可以用一条连接(i,0)和(i,Hi)的线段表示，其中Hi为第i栋楼房的高度。如果这栋楼房上任何一个高度大于0的点与(0,0)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了M天。初始时，所有楼房都还没有开始建造，它们的高度均为0。在第i天，建筑队将会将横坐标为Xi的房屋的高度变为Yi(高度可以比原来大---修建，也可以比原来小---拆除，甚至可以保持不变---建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后，他能看到多少栋楼房？
n,m<=10^5
省队集训讲到了这东西是个经典模型 我听的一脸懵 赶紧补一发
简单点说就是要动态维护上升子序列长度
考虑线段树，每个线段记录只考虑这个区间的答案 顺便记下区间最大值
考虑合并
如果右区间最大值小等于左区间，那么显然右区间不会贡献答案。
不然的话考虑右区间的两个子区间L,R在左区间的限制下能产生的贡献
如果右区间的左区间L的最大值也小等于左区间的最大值，那么直接递归区间R考虑即可。
不然的话，递归考虑区间L，这时候左区间相当于对区间R没有限制，所以这时候区间R贡献的答案是右区间的答案减去区间L的答案。
复杂度显然是nlog^2n的
#include<iostream> #include<cstdio> #define MN 100000 using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x; } struct{int l,r,ans;double mx;}T[MN*4+5]; int n,m; int Calc(int x,double v) { if(T[x].l==T[x].r) return T[x].mx>v; if(T[x<<1].mx>v) return Calc(x<<1,v)+T[x].ans-T[x<<1].ans; else return Calc(x<<1|1,v); } void update(int x) { int l=x<<1,r=x<<1|1; T[x].ans=T[l].ans; T[x].mx=max(T[l].mx,T[r].mx); if(T[r].mx>T[l].mx) T[x].ans+=Calc(r,T[l].mx); } void Build(int x,int l,int r) { T[x].mx=0;T[x].ans=1; if((T[x].l=l)==(T[x].r=r))return; int mid=l+r>>1; Build(x<<1,l,mid); Build(x<<1|1,mid+1,r); } void Modify(int x,int k,double v) { if(T[x].l==T[x].r){T[x].mx=v;return;} int mid=T[x].l+T[x].r>>1; Modify(x<<1|(k>mid),k,v); update(x); } int main() { n=read();m=read(); Build(1,0,n); for(int i=1,j;i<=m;++i) j=read(),Modify(1,j,(double)read()/j),printf("%d ",T[1].ans-1); return 0; }