之前不知为何记得这个是树套树好题于是抽空做了一下。思索很久无果。

感觉倒是线段树还有分块做法一下就想出来了。。（其实线段树做法是因为刚好做过一道差不多的题才会做= =）

线段树做法很优美啊：

维护每段区间的答案。还有这个答案的右端点。

Update的时候套个询问就好了。具体可以看这里。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
double bd[N*4];int Ans[N*4],n,m;
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline double max(double x,double y)
 {return x<y?y:x;}
int Query(int x,int y,int z,double o)
 {
 	int i=x + y >> 1,j=z << 1;
 	if (x==y) return bd[z]>o;
 	if (bd[j]<=o) return Query(i+1,y,j+1,o); else
 	  return Ans[z]-Ans[j]+Query(x,i,j,o);
 }
void Modify(int x,int y,int z,int o,double p)
 {
 	int i=x + y >> 1,j=z << 1;
 	if (x==y) {Ans[z]=1;bd[z]=p;return;}
 	if (o<=i) Modify(x,i,j,o,p); else
 	  Modify(i+1,y,j+1,o,p);
 	bd[z]=max(bd[j],bd[j+1]);
 	Ans[z]=Ans[j]+Query(i+1,y,j+1,bd[j]);
 	return;
 }
int main()
 {
 	n=Read();m=Read();
 	while (m--)
 	 {
 	 	int k=Read(),l=Read();Modify(1,n,1,k,l*1.0/k);
 	 	printf("%d\n",Ans[1]);
 	 }
 	return 0;
 }