楼房重建
维护每个区间从左边开始上升，维护上升的数量
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n, m, x, y;
struct Tree{
int l,r,cnt;
double mx;
}tr[N<<2];
int cal(int rt, double x){
int res = 0;
if(tr[rt].mx <= x) return 0;
if(tr[rt].l == tr[rt].r) return tr[rt].mx > x;
if(tr[rt<<1].mx > x)
res = tr[rt].cnt - tr[rt<<1].cnt + cal(rt<<1, x);//右区间的长度全部加上，递归左区间
else
res = cal(rt<<1|1, x);
return res;
}
void pushup(int rt){
tr[rt].mx = max(tr[rt<<1].mx, tr[rt<<1|1].mx);
int ans = cal(rt<<1|1, tr[rt<<1].mx);
tr[rt].cnt = tr[rt<<1].cnt + ans;
}
void build(int rt, int l, int r){
tr[rt].l = l, tr[rt].r = r;
if(l == r){
// tr[rt].mx = 0.0;
// tr[rt].cnt = 0;
return;
}
int mid = (l+r)>>1;
build(rt<<1, l, mid);
build(rt<<1|1, mid+1, r);
}
void update(int rt, int pos, double v){
if(tr[rt].l == tr[rt].r){
tr[rt].mx = v;
tr[rt].cnt = 1;
return;
}
int mid = (tr[rt].l + tr[rt].r)>>1;
// cout<<rt<<" "<<tr[rt].l<<" "<<tr[rt].r<<" "<<mid<<endl;
if(pos <= mid) update(rt<<1, pos, v);
else update(rt<<1|1, pos, v);
pushup(rt);
}
int main(){
// freopen("slf.out","w",stdout);
cin>>n>>m;
build(1,1,n);
for(int i = 1; i <= m; i++){
cin>>x>>y;
update(1, x, y*1.0/x);
cout<<tr[1].cnt<<endl;
}
return 0;
}
/*
4 3
3 9
4 7
1 1
10 100
6 166267291
4 764085103
1 12360641
1 846991393
6 383204345
2 69698641
9 12331341
1 772764651
5 131311041
10 46049537
6 690746401
2 145679903
10 758217
4 201987721
9 249525949
7 161049529
6 110578175
4 231517001
5 644489651
7 340648201
7 151799407
10 7480386
3 206257865
9 328935144
3 352739143
7 84581584
5 29535731
4 196598419
6 55312269
8 11283241
7 10289281
4 250134981
2 208241815
5 46222012
6 34664323
7 359037865
9 396005251
2 101892805
2 210317844
3 441658977
5 113743513
8 44192926
6 102944206
4 288727385
6 233930929
8 2996745
2 660629278
4 32747101
5 7218281
9 991959715
1 130023361
9 20174977
10 590823439
4 609043601
10 794927517
8 835448158
9 79194028
10 218902057
3 81328780
1 842713384
6 506252986
9 38734669
7 134763046
7 198136601
6 145100953
8 139458607
3 621701089
10 163368301
8 162641963
2 177393360
8 429881306
7 165305441
4 16342951
10 217025793
5 32343754
1 221071391
4 17866381
2 1999669
2 109659346
10 179614829
4 59706591
4 19298137
8 774219601
8 6099164
7 258624081
5 66188305
5 64116244
10 355183187
2 354022111
6 3929553
3 234438274
5 550657829
1 283731112
1 497844261
7 287715541
7 434450329
10 267779521
5 37026775
9 7125790
7 23094767
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
*/