洛谷P4198_楼房重建_分块

需要O2优化

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
vector<double> st[(int)1e3+9];

ll n,m,id[(int)1e5+9],fk,l[(int)1e5+9],r[(int)1e5+9];
double a[(int)1e5+9];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    fk=sqrt(n*log(n)/2);
    for(int i=1;i<=n;++i){
        id[i]=(i-1)/fk+1;
        if(!l[id[i]])l[id[i]]=i;
        r[id[i]]=i;
    }
    for(int i=1,x,y;i<=m;++i){
        cin>>x>>y;
        auto &it=st[id[x]];
        a[x]=1.0*y/(x*1.0);
        it.clear();
        for(int j=l[id[x]];j<=r[id[x]];++j){
            if(a[j]==0.0)continue;
            if(it.empty()||it.back()<a[j])it.push_back(a[j]);
        }
        ll ans=0;
        double mx=0.0;
        for(int j=1;j<=id[n];++j){
            auto &aa=st[j];
            if(!aa.empty()){
                ans+=aa.end()-upper_bound(aa.begin(),aa.end(),mx);
                mx=max(mx,aa.back());
            }
        }
        cout<<ans<<"\n";
    }
}