因为有个bool调了一个小时，汤碗里。
显然能看到是斜率的问题，后面的斜率要严格大于前面的斜率才能够看见，所以这就是最大严格前缀长度问题。
有修改考虑线段树维护，信息合并时并不能直接合并，左部分可以直接合并，但右部分不能超过左部分的斜率最大值，所以我们用函数递归右区间判断，如果当前部分左区间的斜率最大值大于 \(K\)，那右边全部合法，左边部分合法，函数调用左边，否则只有右边部分合法，函数递归调用右边。
真的要注意维护斜率，线段树上要维护斜率最大值所在的下标，判断斜率大小时返回 bool，我因此调了 \(1\) 个小时。
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define ls p<<1
#define rs p<<1|1
#define re register
#define pb push_back
#define pir pair<int,int>
#define f(a,x,i) for(int i=a;i<=x;i++)
#define fr(a,x,i) for(int i=a;i>=x;i--)
#define lb(x) x&(-x);
const int N=1<<18|7;
const int mod=1e9+7;
using namespace std;
int n,m;
int mx[N],H[N];
int cnt[N];
bool gt(int p1,int p2){
if(!p2) return H[p1];
return (ll)H[p1]*p2>(ll)H[p2]*p1;
}
int fs(int p,int k,int l,int r){
if(l==r) return gt(l,k);
int mid=(l+r)>>1;
if(gt(mx[ls],k)){
return fs(ls,k,l,mid)+cnt[p]-cnt[ls];
}
else{
return 0+fs(rs,k,mid+1,r);
}
}
void change(int p,int l,int r,int pos){
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) change(ls,l,mid,pos);
else change(rs,mid+1,r,pos);
mx[p]=gt(mx[rs],mx[ls])?mx[rs]:mx[ls];
cnt[p]=cnt[ls]+fs(rs,mx[ls],mid+1,r);
}
void build(int p,int l,int r){
mx[p]=l,cnt[p]=1;
if(l==r) return;
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
}
signed main(){
// freopen("xp1.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(nullptr);
cin>>n>>m;
build(1,1,n);
while(m--){
int pos,x;
cin>>pos>>x;
H[pos]=x;
change(1,1,n,pos);
cout<<fs(1,0,1,n)<<"\n";
}
return 0;
}