CF1870G MEXanization

,

Description

https://www.luogu.com.cn/problem/CF1870G

Solution

很好的题目。

首先发现除了第一个答案是不降的，这启发我们转化为判断问题。来判断能否得出 $k$。

先考虑一个暴力，从 $k-1$ 开始从大到小枚举。维护每个权值所至少需要的个数。初始 $[0,k-1]$ 都至少需要 $1$。记当前枚举到 $x$。如果 $x$ 的个数大于等于所需要的，则把多出的部分变成 $0$。否则令其需要至少还需要 $k$ 个，加到 $[0,x-1]$ 中。

然后我们还有一个观察，由于总共只有 $n$ 个数，如果需要的已经大于 $n$ 了那么肯定不合法。又因为还需要的每个数都只会算一遍，所以如果合法，还需要的数是 $O(\sqrt n)$ 级别的。

然后我们可以用线段树维护区间最小值来优化这个过程。又因为遍历是有顺序的，所以可以在线段树上依次遍历一起做。总共遍历到的节点是 $O(\sum \dfrac{\sqrt n}{2^k})=O(\sqrt n)$ 的。单次判断的复杂度是 $O(\sqrt n)$ 的，因为答案的上界是 $n+1$，所以复杂度就是 $O(n\sqrt n)$。

而且感觉这题数据很难造所以跑不满。

具体实现上特殊处理 $0$ 的个数，而维护 $0$ 的个数又可以维护一个区间和。在遍历的时候更新加在 $0$ 上面的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
ll power(ll x,int y=mod-2,int p=mod) {
	ll sum=1;x%=p;
	while (y) {
		if (y&1) sum=sum*x%p;
		x=x*x%p;y>>=1;
	}
	return sum;
}
int n,a[maxn],N;
int f[maxn<<2],s[maxn<<2];
void Update(int l,int r,int rt,int head,int k) {
	if (l==r) return f[rt]+=k,s[rt]+=k,void();
	int mid=l+r>>1;
	if (head<=mid) Update(l,mid,rt<<1,head,k);
	else Update(mid+1,r,rt<<1|1,head,k);
	f[rt]=min(f[rt<<1],f[rt<<1|1]);
	s[rt]=s[rt<<1]+s[rt<<1|1];
}
int Query(int l,int r,int rt,int head,int tail) {
	if (head<=l&&r<=tail) return s[rt];
	int mid=l+r>>1,sum=0;
	if (head<=mid) sum+=Query(l,mid,rt<<1,head,tail);
	if (tail>mid)  sum+=Query(mid+1,r,rt<<1|1,head,tail);
	return sum;
}
int lazy,nums,cnt,flag;
void calc(int l,int r,int rt,int tail) {
	if (r<=tail&&f[rt]>=lazy) return nums+=s[rt]-(r-l+1)*lazy,void(); 
	if (!flag) return ;
	if (l==r) {
		if (l==0) {
			flag&=(s[rt]+nums>=lazy);
		}
		else {
			cnt+=(lazy-f[rt])*l-lazy;
			lazy+=lazy-f[rt];
			if (cnt>n) flag=0;
		}
		return ;
	}
	int mid=l+r>>1;
	if (tail>mid) calc(mid+1,r,rt<<1|1,tail); 
	if (!flag) return ;
	calc(l,mid,rt<<1,tail);
}
bool check(int val) {
	lazy=1;flag=1;cnt=0;nums=0;
	if (val<N) nums=Query(0,N,1,val+1,N);
	calc(0,N,1,val);
	return flag;
}
void solve(void) {
	int i;
	read(n);N=n+1;
	fill(f,f+4*n+1,0);
	fill(s,s+4*n+1,0);
	for (i=1;i<=n;i++) read(a[i]);
	printf("%d ",a[1]==0?1:a[1]);Update(0,N,1,a[1],1);
	int k=0;
	for (i=2;i<=n;i++) {
		Update(0,N,1,a[i],1);
		while (check(k)) k++;
		printf("%d ",k);
	}
	put();
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();	
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i