P4198 楼房重建

参考博客

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
int n,m;
ll tr[N<<2];  //tr[p]表示斜率递增的长度 
double minx[N<<2],maxn[N<<2];
ll ask(int p,int l,int r,double z){
    if(l==r) return maxn[p]>z;
    int mid=(l+r) >> 1;
    if(maxn[p*2]<=z) return ask(p*2+1,mid+1,r,z);
    if(minx[p*2]>=z) return tr[p];
    return tr[p]-tr[p*2]+ask(p*2,l,mid,z) ;
}
void add(int p,int l,int r,int pos,double w){
    if(l==r){
        tr[p]=1;minx[p]=1.0*w/pos;
        maxn[p]=1.0*w/pos;return ;
    }
    int mid=(l+r) >> 1;
    if(pos<=mid) add(p*2,l,mid,pos,w);
    if(mid+1<=pos) add(p*2+1,mid+1,r,pos,w);
    tr[p]=tr[p*2]+ask(p*2+1,mid+1,r,maxn[p*2]);
    maxn[p]=max(maxn[p*2],maxn[p*2+1]);
    minx[p]=min(minx[p*2],minx[p*2+1]); 
}
int main(){
    cin >> n >> m;
    int x,w;
    while(m--){
        cin >> x >> w;
        add(1,1,n,x,1.0*w/1);
        cout << tr[1] << "\n";
    }
    return 0;
}