专栏文章

题解：CF1870G MEXanization

NNetheris10+7
CF1870G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minn7zox
此快照首次捕获于
2025/12/02 05:10
3 个月前
此快照最后确认于
2025/12/02 05:10
3 个月前
查看原文
首先容易发现，除了第一个数以外，后面的 n−1n-1 个前缀的答案都是单调不降的，证明这是显然的。
于是我们考虑去 check 每个数是否能成为答案。
对于一个数 xx，我们考虑这样去 check：
我们设 cnticnt_i 表示 ii 在前缀中出现的次数，那么我们只用满足 ∀i∈[0,x−1]\forall i\in[0,x-1]，都有 cnti≥1cnt_i\ge1。
于是我们直接从大到小扫 ii，如果当前的 cnti≤0cnt_i\le0，那么就用 j∈[0,i−1]j\in [0,i-1] 的 cntjcnt_j 凑出 1−cnti1-cnt_i 个 ii 即可。
这样直接模拟单次 check 能做到 O(n)O(n)，总共就是 O(n2)O(n^2) 的了。
考虑优化，先把上述的贪心换种形式：
我们设 pp 表示当前的 cnticnt_i 要分多少个给 ii 后面的，ss 表示后面的有多少是多余的。
于是我们对于每一个 ii，有 ss 加上 max⁡(0,cnti−p−1)\max(0,cnt_i-p-1)，pp 加上 max⁡(0,1−(cnti−p))\max(0,1-(cnt_i-p))。
其实容易发现，我们 pp 的有效加操作是只有 n\sqrt n 次的。
考虑证明，由于 ∑cnt\sum cnt 是 O(n)O(n) 量级的，而我们 pp 减的总数应该是 p×(p+1)2\frac{p\times(p+1)}{2}，所以 pp 自然是 O(n)O(\sqrt n) 量级的。
于是我们直接用线段树二分去找 pp 的有效操作，这样就是 O(nnlog⁡n)O(n\sqrt n\log n) 的。
接着考虑优化，由于直接找是真的没什么前途，所以我们考虑直接 dfs 线段树。
设 mnxmn_x 表示区间 cnticnt_i 的最小值，sumxsum_x 表示区间 cnticnt_i 的和。
还是考虑我们刚刚的做法，在线段树上，我们依旧从后往前，但是时间复杂度是不变的。
考虑剪枝一下，也就是对于线段树上节点 (x,l,r)(x,l,r)：如果 mnx−1≥pmn_x-1\ge p，那么 ss 加上 sumx−(r−l+1)(p+1)sum_x-(r-l+1)(p+1)，然后返回。
发现这样写了后就可以通过了。
考虑分析一下时间复杂度：我们一层一层考虑，对于所有大小为 2k2^k 的区间从左到右第 xx 个节点，若它的子树中有至少一个可以贡献的 pp，那么 ∑cntj\sum cnt_j 会至少减少 x2kx2^k，所以不同的 xx 最多 n2k\sqrt{\dfrac{n}{2^k}} 种。对每一层求和后明显发现总量是 O(n)O(\sqrt n) 量级的。
总时间复杂度为 O(nn)\mathcal{O}(n\sqrt{n})。
CPP
#include<bits/stdc++.h>
#define ll long long
#define pc putchar
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
int pstk[40];
inline void write(int x){
	if(!x)return putchar('0'),void();
	if(x<0)putchar('-'),x=-x;
	int len=0;for(;x;x/=10)pstk[++len]=x%10;
	while(len)putchar(pstk[len--]+'0');
}
const int Maxn=2e5+5;
int n,a[Maxn];
struct Tree{int data,mn;}t[Maxn<<2];
int V[Maxn];
void build(int x,int l,int r){
	if(l==r)return void(t[x]={0,0});
	int mid=l+r>>1;
	build(x<<1,l,mid);build(x<<1|1,mid+1,r);
}
void change(int x,int l,int r,int d,int p){
	if(l==r){t[x].data+=p;t[x].mn+=p;return;}
	int mid=l+r>>1;
	if(mid>=d)change(x<<1,l,mid,d,p);
	else change(x<<1|1,mid+1,r,d,p);
	t[x].mn=min(t[x<<1].mn,t[x<<1|1].mn);
	t[x].data=t[x<<1].data+t[x<<1|1].data;
}
int cnt[Maxn];
int ok;
void dfs(int x,int l,int r,int R,ll&d,ll&z){
	if(ok)return;
	if(t[x].mn-1>=d&&r<=R){
		z+=1ll*t[x].data-1ll*(d+1)*(r-l+1);
		return;
	}
	if(l==r){d+=1ll-1ll*(t[x].data-d);if(d>n)ok=1;return;}
	int mid=l+r>>1;
	if(mid<R)dfs(x<<1|1,mid+1,r,R,d,z);dfs(x<<1,l,mid,R,d,z);
}
inline bool check(int x){
	ll d=0,z=0;
	ok=0;if(x>1)dfs(1,1,n,x-1,d,z);
	if(z+cnt[0]-d>=1){
		cnt[0]-=V[x];cnt[x]=V[x];
		change(1,1,n,x,V[x]);
		return true;
	}
	return false;
}
inline void solve(){
	n=read();
	int ans=1;build(1,1,n);
	for(int i=0;i<=n+1;i++)V[i]=cnt[i]=0;
	for(int i=1;i<=n;i++){
		a[i]=read();
		V[a[i]]++;
		if(a[i]>=ans||!a[i])cnt[0]++;
		else change(1,1,n,a[i],1),cnt[a[i]]++;
		if(i==1)write(max(1,a[i])),pc(' ');
		else{
			while(check(ans))ans++;
			write(ans-1);pc(' ');
		}
	}
	pc('\n');
}
int main(){
	int T=read();
	while(T--)solve();
	return 0;
}
/*
20
18 12 18 6 4 14 11 5 8 8 6 11 11 6 18 2 1 6 13 11 

1
6
4 3 0 0 0 0
*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...