随机说话
这个题做法没见过记一下。
我一开始以为是李超树的题，结果把李超树打上之后就不会做了。
然后题读错了写了一个弱化版。
题目分析
做法参考
这个题题意只是假装是一个有关线段的题。
简化之后的题意如下。
有一个初始都为 \(0\) 的实数数列，每一次会修改位置 \(x\) 的数为 \(k\)（其中 \(k=\frac{y}{x}\)）。求每次修改之后从第一个位置开始以下列规则选择的数列的长度。
如果在 \(x\) 位置之前选择的数列中没有大于 \(k_x\) 的数，就选择 \(k_x\)。
这个题需要一个数据结构来维护。
数据结构的选取需要题目性质的分析。
经下面分析可以得到需要的数据结构是线段树。
题目很重要的性质是这个选取数列的方法。
很容易发现我们选出的这个数列是单调的，而且一定会选 \(k_1\) 和最大的 \(k\)。
我们考虑区间选取的数列进行合并的过程。
对于两个有左右顺序的数列，发现左边的数列里的数是一定会被选的。
而右边的数列中小于左边数列的 \(k\) 的最大值的数 \(k_{max}\) 都不会被选，反之如果右边选取的第一个数就大于 \(k_{max}\) 就会全选右边的。
除了这两种情况的一般情况，我们就需要找到右边被选取的第一个 \(k_x\)，由于单调性的原因是 \(k_x\) 左边都不会被选，\(k_x\) 的右边都会被选。
于是我们可以考虑这个区间分出来的两个子区间，下列的左右区间都指这两个子区间。
如果左区间的最大值小于等于 \(k_{max}\) 就都不会选，与右区间进行合并即可。
而左区间的最大值大于 \(k_{max}\) 的时候，右侧选出的一定会被选，左区间合并之后直接累加右区间选的即可。
到此为止，我们就找到了一个复杂度为 \(O(\log n)\) 的 pushup 的方法。
用线段树来维护数据，单点修改需要 pushup \(\log n\) 次，查询的时间复杂度仅为 \(O(1)\)，总的时间复杂度为 \(O(\log ^2n)\)，可以通过此题。
代码如下。
//照https://www.luogu.com.cn/article/0xufwccu打的
#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=1e5+10;
constexpr double eps=1e-12;
int n,m;
double k[MAXN];
struct SegmentTreeNode{
double maxk;
int ans;
#define k(id) segt[(id)].maxk
#define ans(id) segt[(id)].ans
}segt[MAXN<<2];
int cmp(double x,double y){
if(x-y>eps)return 1;
else if(y-x>eps)return -1;
else return 0;
}
#define lid (id<<1)
#define rid ((id<<1)|1)
#define mid ((l+r)>>1)
void pushup(int id){
k(id)=max(k(lid),k(rid));
}
int query(int id,int l,int r,double mk){
if(cmp(k[l],mk)==1)return ans(id);
if(cmp(k(id),mk)==-1)return 0;
if(l==r)return cmp(k(id),mk)==1;
if(cmp(k(lid),mk)==1)return query(lid,l,mid,mk)+ans(id)-ans(lid);
else return query(rid,mid+1,r,mk);
}
void change(int id,int l,int r,int loc){
if(l==r){
k(id)=k[l];
ans(id)=1;
return;
}
if(loc<=mid)change(lid,l,mid,loc);
else change(rid,mid+1,r,loc);
pushup(id);
ans(id)=ans(lid)+query(rid,mid+1,r,k(lid));
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<=m;++i){
scanf("%d%d",&x,&y);
k[x]=1.0*y/x;
change(1,1,n,x);
printf("%d\n",ans(1));
}
return 0;
}