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
2 4
3 6
1 1000000000
1 1
Sample Output
1
1
2
数据约定
对于所有的数据1<=Xi<=N，1<=Yi<=10^9
N,M<=100000
思路
恩。。网上用分块做的居多。那我们就用线段树做吧！
对于[l,r]建立一个节点，记录下从l节点开始的最长上升序列的长度以及在哪里结尾，这样上升子序列的最大值也知道了。
然后两个区间怎么合并呢？
如果左子树的最高点比右子树最左边的点还要高，那么就是左子树。
不然就在右子树中找，小于等于左子树最高点的有多少个，记为Rank。结尾变成右子树的结尾，长度变成左子树+右子树-Rank。
如何在一颗子树中找小于等于一个数的点有多少个？实际上跟合并差不多。
如果小于最小点或者大于等于最大点直接返回，不然分情况讨论是不是大于左子树的最大值。
1.不是：在左子树中递归查找
2.是：在右子树中查找出小于这个数的个数Rank，返回Rank-（左子树长度+右子树长度-当前节点的长度）+左子树长度
我特意没有化简表达式。。画个图很明白吧（不要吐槽）
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
const double eps=1e-;
///==============struct declaration==============
struct Seg_Node{
int ed,length;
};
///==============var declaration=================
const int MAXN=;
int n,L,R,m;
long double Building[MAXN];
Seg_Node Seg_Tree[MAXN*],Ans;
///==============function declaration============
void BuildTree(int o,int l,int r);
void Update(int o,int l,int r);
void Query(int o,int l,int r);
int Query(int o,int l,int r,double height);
void Modify(int o,int l,int r,int k,double h);
bool Equal(double a,double b){return fabs(a-b)<=1e-;}
///==============main code=======================
int main()
{
#define FILE__
#ifdef FILE__
freopen("input","r",stdin);
freopen("output","w",stdout);
#endif
scanf("%d%d",&n,&m);
BuildTree(,,n);
Building[]=-;
while (m--){
int X,Y;scanf("%d%d",&X,&Y);
Modify(,,n,X,double(Y)/X);
L=,R=n;
printf("%d\n",Seg_Tree[].length);
}
return ;
}
///================fuction code====================
void BuildTree(int o,int l,int r){
int m=(l+r)>>,lc=o*,rc=o*+;
if (l==r){
Seg_Tree[o].ed=l;
Seg_Tree[o].length=;
return ;
}
BuildTree(lc,l,m);
BuildTree(rc,m+,r);
Update(o,l,r);
}
void Update(int o,int l,int r){
int m=(l+r)>>,lc=o*,rc=o*+;
if (Seg_Tree[rc].length==||Building[Seg_Tree[lc].ed]>=Building[Seg_Tree[rc].ed])
Seg_Tree[o]=Seg_Tree[lc];
else if (Seg_Tree[lc].length==)
Seg_Tree[o]=Seg_Tree[rc];
else{
int Rank=Query(rc,m+,r,Building[Seg_Tree[lc].ed]);
Seg_Tree[o].ed=Seg_Tree[rc].ed;
Seg_Tree[o].length=Seg_Tree[lc].length+Seg_Tree[rc].length-Rank;
}
}
int Query(int o,int l,int r,double height){///Return how many numbers Less than or equal to height
int m=(l+r)>>,lc=o*,rc=o*+;
if (height>=Building[Seg_Tree[o].ed]) return Seg_Tree[o].length;
if (height<Building[l]) return ;
if (height<Building[Seg_Tree[lc].ed]) return Query(lc,l,m,height);
return Seg_Tree[lc].length+Query(rc,m+,r,height)-(Seg_Tree[lc].length+Seg_Tree[rc].length-Seg_Tree[o].length);
}
void Modify(int o,int l,int r,int k,double h){
int m=(l+r)>>,lc=o*,rc=o*+;
if (l==r){
Building[l]=h;
if (!Equal(h,))
Seg_Tree[o].length=;
else
Seg_Tree[o].length=;
}
else{
if (m>=k) Modify(lc,l,m,k,h);
else Modify(rc,m+,r,k,h);
Update(o,l,r);
}
}
BZOJ 2957