P4198题解

· · 题解

题意：单点修改与查询前缀最大值个数。

维护 ans_k 为区间 [l,r] 的答案，怎么由 [l,mid] 和 [mid+1,r] 合并?显然可以直接把左区间的答案加上去，考虑右区间的贡献，右区间的一个前缀最大值，只有它大于左区间的最大值才能对答案有贡献，记这个贡献为 val_{k*2+1} 。首先如果右区间最大值小于左区间最大值，那右区间就没有贡献了；否则，记 [l,mid] 的最大值为 v ，那么我们要求区间 [mid+1,r] 内大于 v 的前缀最大值数。区间 p 满足区间内大于 v 的前缀最大值数记为 cnt_{p,v} ，如果 p 的左儿子最大值 maxn[lc] 小于 v ，那么左儿子不会造成贡献，cnt_{p,v}=cnt_{rc,v} ;如果左儿子最大值大于 v ，则 v 不会对右儿子有约束，于是cnt_{p,v}=cnt_{lc,v}+val_{rc} 。

可见不管哪种情况都只需往一侧递归，复杂度为 O(q \log^2 n) 。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double eps=1e-10;
ll n,q,x,y;
double maxn[400005];
ll ans[400005],val[400005];
bool leaf[400005];
inline ll get(ll k,double v){
    if(leaf[k])return (maxn[k]-v>eps?1:0);
    if(v-maxn[k<<1]>=eps)return get(k<<1|1,v);
    else return 1ll*get(k<<1,v)+val[k<<1|1];
}
void build(ll k,ll l,ll r){
    if(l==r){
        leaf[k]=1;
        return ;
    }
    ll mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}
void modify(ll k,ll l,ll r,ll x,ll v){
    if(l==r&&l==x){
        maxn[k]=1.0*v/x;
        if(maxn[k]>eps)ans[k]=1;
        return ;
    }
    ll mid=(l+r)>>1;
    if(x<=mid)modify(k<<1,l,mid,x,v);
    else modify(k<<1|1,mid+1,r,x,v);
    if(maxn[k<<1]-maxn[k<<1|1]>=eps)val[k<<1|1]=0;
    else val[k<<1|1]=get(k<<1|1,maxn[k<<1]);
    ans[k]=1ll*ans[k<<1]+val[k<<1|1];
    maxn[k]=max(maxn[k<<1],maxn[k<<1|1]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    build(1,1,n);
    while(q--){
        cin>>x>>y;
        modify(1,1,n,x,y);
        cout<<ans[1]<<"\n";
    }
    return 0;
}