#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[300010],dp[300010],la[300010],ans[300010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	int l=0,cnt=0;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		l=max(l,la[a[i]]);
		cnt+=!la[a[i]];
		la[a[i]]=i;
		if(i-l==cnt&&dp[l]!=-1)dp[i]=dp[l]+1;
		else dp[i]=-1;
	}
	int p=-1;
	for(int i=m;i>=l;i--){
		if(dp[i]!=-1&&p==-1)p=i;
		else if(dp[i]!=-1&&dp[i]<dp[p])p=i;
	}
	if(p==-1){
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=n;i++)ans[i]=dp[p]+1;
	for(int i=1;i<=p;i++)ans[a[i]]--;
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	return 0;
}

Problem Link

题目大意

给定序列 $b_1\sim b_m$，构造一个长度为 $n$ 的序列 $a_1\sim a_n$，使得第 $i$ 次操作前 $a_{b_i}=\min a_{1\sim n}$，操作后给 $a_{b_i}$ 加一，求字典序最小解。

数据范围：$n,m\le 3\times 10^5$。

思路分析

观察 $b$ 的操作过程，把 $a_{b_i}$ 相同的若干操作划分成一段，那么每次操作会让所有最小值 $+1$。

对于同一段的操作，不可能有 $b_i$ 相等，并且上一段的 $b_i$ 会被下一段的 $b_i$ 包含。

不难发现满足这两个条件的划分方式一定是合法的，并且我们只要最小化划分轮数即可求出字典序最小解。

设 $f_i$ 表示 $b[1,i]$ 的最小划分轮数，容易发现左端点 $l$ 有一个下界，并且要求 $b[1,l)$ 的数被 $b[l,i]$ 包含，显然 $l$ 越小越好，因此可以直接贪心。

注意最后一轮可以不划分满，即在倒数第二轮所有可能的终止点 $i$ 中取 $f_i$ 最小的一个，重复时取 $i$ 最大的一个。

时间复杂度 $\mathcal O(n+m)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
int n,m,a[MAXN],pre[MAXN],dp[MAXN],ans[MAXN];
signed main() {
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	int lst=0,cnt=0;
	for(int i=1;i<=n;++i) {
		lst=max(lst,pre[a[i]]),cnt+=!pre[a[i]],pre[a[i]]=i;
		if(i-lst==cnt&&~dp[lst]) dp[i]=dp[lst]+1;
		else dp[i]=-1;
	}
	int o=-1;
	for(int i=n;i>=lst;--i) if(~dp[i]&&(o==-1||dp[i]<dp[o])) o=i;
	if(o==-1) return puts("-1"),0;
	for(int i=1;i<=m;++i) ans[i]=dp[o]+1;
	for(int i=1;i<=o;++i) --ans[a[i]];
	for(int i=1;i<=m;++i) printf("%d ",ans[i]); puts("");
	return 0;
}