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)

。

CPP

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

文章操作

相关推荐

评论

P4198题解