1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=1e5+9;
double mx[maxn<<2];
ll ans[maxn<<2],n,m;
ll query(int l,int r,int k,double ma){
if(mx[k]<=ma)return 0;
if(l==r)return 1;
else if(mx[k<<1]<=ma)return query(((l+r)>>1)+1,r,k<<1|1,ma);
return query(l,(l+r)>>1,k<<1,ma)+ans[k]-ans[k<<1];
}
void change(int l,int r,int k,int x,double val){
if(l==x&&r==x)return ((void)(ans[k]=1,mx[k]=val));
int mid=(l+r)>>1;
if(x<=mid)change(l,mid,k<<1,x,val);
else change(mid+1,r,k<<1|1,x,val);
mx[k]=max(mx[k<<1],mx[k<<1|1]);
ans[k]=ans[k<<1]+query(mid+1,r,k<<1|1,mx[k<<1]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1,x,y;i<=m;++i){
cin>>x>>y;
change(1,n,1,x,(y*1.0)/(x*1.0));
cout<<ans[1]<<"\n";
}
}
|