题解：CF2146E Yet Another MEX Problem

我们考虑对于每个右端点 $i$ ，选择枚举 $[l,i]$ 的区间 $\text{MEX}=x$ 。
注意到直接枚举 $x$ 是不容易做的，因为我们没办法钦定 $[0,x)$ 全部出现；但是只要 $x$ 没有出现，就一定有 $\text{MEX}\leq x$ ，而此时 $x$ 的贡献不优，因此这么做不会算大贡献。
现在考虑如何维护每个 $x$ 的贡献。设 $x$ 上一次出现的位置为 $p$ （特别地，没有出现则为 $0$ ），那么由于 $x$ 不能出现，所以有 $l>p$ 。此时显然令 $l=p+1$ 最优，贡献就是 $\sum\limits_{k=p+1}^i [a_k>x]$ 。
发现这个贡献形式非常平凡，每次加入 $a_i$ 的时候对于 $x<a_i$ 的 $x$ 贡献加一即可。另外加入的时候还要注意特殊更新 $x=a_i$ 的情况，将它的贡献置为 $0$ 。
现在需要支持的操作是区间加，单点赋值和全局查询。显然可以线段树维护之，复杂度 $O(n\log n)$ 。

好久没写线段树了。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 7;
int n,m;
int tr[N*4],tag[N*4];
void pushdown(int x){
	tag[x*2] += tag[x];
	tag[x*2+1] += tag[x];
	tr[x*2] += tag[x];
	tr[x*2+1] += tag[x];
	tag[x] = 0;
}
void build(int x,int l,int r){
	tr[x] = tag[x] = 0;
	if(l==r){
		return;
	}
	int mid = (l+r)/2;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	tr[x] = max(tr[x*2],tr[x*2+1]);
}
void update(int x,int l,int r,int L,int R){
	if(L>r || l>R) return;
	if(l<=L && R<=r){
		tr[x] += 1;
		tag[x] += 1;
		return;
	}
	pushdown(x);
	int mid = (L+R)/2;
	update(x*2,l,r,L,mid);
	update(x*2+1,l,r,mid+1,R);
	tr[x] = max(tr[x*2],tr[x*2+1]);
}
void mdf(int x,int l,int r,int pos){
	if(l==r){
		tr[x] = 0;
		return;
	}
	pushdown(x);
	int mid = (l+r)/2;
	if(pos<=mid) mdf(x*2,l,mid,pos);
	else mdf(x*2+1,mid+1,r,pos);
	tr[x] = max(tr[x*2],tr[x*2+1]);
}
void solve(){
	cin>>n;
	build(1,0,n);
	for(int i=1;i<=n;++i){
		int x;cin>>x;
		update(1,0,x-1,0,n);
		mdf(1,0,n,x);
		cout<<tr[1]<<' ';
	}
	cout<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;cin>>T;
	for(int _=1;_<=T;++_){
		solve();
	}
	return 0;
}

题解：CF2146E Yet Another MEX Problem

文章操作

相关推荐

评论

题解：CF2146E Yet Another MEX Problem