线段树
//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#define lc x<<1
#define rc x<<1|1
#define mid ((l+r)>>1)
const int maxn=;
int a,b,n,m,sg[maxn<<];
double sgd[maxn<<];
using namespace std;
inline int read(){
int ret=,f=; char ch=getchar();
while((ch!='-')&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) ret=ret*+ch-'';
return ret*f;
}
int CUL(double ma,int x,int l,int r){
if(l==r) {return sgd[x]>ma;}
if(sgd[lc]<=ma) return CUL(ma,rc,mid+,r);
else return sg[x]-sg[lc]+CUL(ma,lc,l,mid);
}
void change(int x,int l,int r,int xx,double w){
if(l==r) {sg[x]=; sgd[x]=w;return;}
if(xx<=mid) change(lc,l,mid,xx,w);
else change(rc,mid+,r,xx,w);
sgd[x]=max(sgd[lc],sgd[rc]);
sg[x]=sg[lc]+CUL(sgd[lc],rc,mid+,r);
}
int main()
{
n=read(); m=read();
while(m--){
a=read(); b=read();
change(,,n,a,(double)b/a);
printf("%d\n",sg[]);
}
return ;
}
BZOJ 2957楼房重建