洛谷P4198_楼房重建

#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";
    }
}