传送门
分析
被线段树按在地上摩擦 先把左边转化成斜率，那么这个题就转化成每次修改一个点的值，输出前缀最大值的个数
看到标签是线段树，所以还是想想线段树的做法吧
既然是线段树，那么就要将区间分成两半，那么左半区间可以直接递归下去做，右半区间就要考虑左半区间对它的影响
左半区间的最大值会对右半区间的前缀最大值的个数造成影响，所以询问时应该带上之前的最大值
考虑一次询问(l,r,x)，表示l前面的数的最大值为x，区间(l,r)内的前缀最大值，那么每次就要输出询问(1,n,0)
用dp式子转移的思想对询问进行拆分
设mid=(l+r)/2，mx(l,r)表示l到r内的最大值
如果x>mx(l,mid),那么就左半区间就不可能存在前缀最大值，(l,r,x)的结果就等于(mid,r,x)
如果x<=mx(l,mid),那么询问(l,r,x)就可以拆成(l,mid,x)与(mid+1,r,mx(l,mid))。
注意到(mid+1,r,mx(l,mid))这个东西与x无关，可以在插入值的时候就处理它
所以对于每个询问(l,r,x)真正需要现场求的是(l,mid,x)或(mid,r,x),每次拆分区间长度减半，可以做到logn的复杂度
至于每次插入值修改(mid+1,r,mx(l,mid))时，也可以用同样的方法，总共有logn个区间,每个区间处理的复杂度为logn,所以为long^2n的复杂度
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,vr[maxn<<];double mx[maxn<<];
int que(int id,int l,int r,double L)
{
if(l==r)return mx[id]>L?:;
int mid=(l+r)>>;
if(L<=mx[id<<])return que(id<<,l,mid,L)+vr[id];
else return que(id<<|,mid+,r,L);
}
void fix(int id,int l,int r,int k,double v)
{
if(l==r){mx[id]=v;return;}
int mid=(l+r)>>;
k<=mid?fix(id<<,l,mid,k,v):fix(id<<|,mid+,r,k,v);
mx[id]=max(mx[id<<],mx[id<<|]);vr[id]=que(id<<|,mid+,r,mx[id<<]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,x,y;i<=m;i++)
scanf("%d%d",&x,&y),
fix(,,n,x,double(y)/double(x)),
printf("%d\n",que(,,n,));
}