题意：转换成斜率然后维护区间的上升序列(从区间第一个数开始的单调上升序列)
区间保存这个区间的最长序列的长度$ls$和最大值$mx$
如何合并两个区间信息？
左区间一定选择，右区间递归寻找第一个大于左区间最大值$v$的位置
具体来看，如果右区间的左最大值$<v$那么左面不可能选递归右面
否则这个区间所选的右面一定选，减去左面的$ls$再递归左面
合并复杂度$O(logn)$，总复杂度$O(nlog^2n)$
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lc x<<1
#define rc x<<1|1
#define mid ((l+r)>>1)
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
using namespace std;
typedef long long ll;
const int N=1e5+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,Q,a,b;
struct Node{
int ls;
double mx;
Node():ls(),mx(0.0){}
}t[N<<];
int cal(int x,int l,int r,double v){
if(l==r) return t[x].mx>v;
if(t[lc].mx<=v) return cal(rson,v);
else return t[x].ls-t[lc].ls+cal(lson,v);
}
inline void merge(int x,int l,int r){
t[x].mx=max(t[lc].mx,t[rc].mx);
t[x].ls=t[lc].ls+cal(rson,t[lc].mx);
}
void segCha(int x,int l,int r,int p,double v){
if(l==r) t[x].ls=,t[x].mx=v;
else{
if(p<=mid) segCha(lson,p,v);
if(mid<p) segCha(rson,p,v);
merge(x,l,r);
}
}
int main(){
freopen("in","r",stdin);
n=read();Q=read();
while(Q--){
a=read();b=read();
segCha(,,n,a,(double)b/a);
printf("%d\n",t[].ls);
}
}