ARC130E Increasing Minimum 做题记录

对于一个长 $n$ 的正整数序列 $A$，定义一个长 $m$ 的，值域 $[1,n]$ 的正整数序列 $b$ 关于 $A$ 是好的当且仅当：

• 从前往后遍历 $b$，遍历到 $i$ 时：
  1. 需要满足 $A_{b_i}=\min\limits_{j=1}^n\{A_j\}$；
  2. 将 $A_{b_i}$ 增加 $1$；

现给定 $n,m$ 和序列 $b$，你需要构造一个长 $n$ 的字典序最小的正整数序列 $A$，使得 $b$ 关于 $A$ 是好的，或报告无解。

$1\le n,m\le 3\times 10^5$。

考虑操作的过程，不难发现相当于不断把最小值的位置抬上去，所以操作时序列 $A$ 的最小值一定是单调不降的。

考虑按照操作时 $A$ 的最小值将 $b$ 分段，不难发现一个分段方式合法（存在对应的 $A$）当且仅当：

• 每一段中的数互不相同；
• 除了最后一段外，第 $i$ 段的数构成的集合包含第 $i-1$ 段的数构成的集合；

第二个限制也相当于要求每一段 $[l,r]$ 中的数的集合包含 $b_{[1,l-1]}$ 中的数的集合。

显然若一段以 $i$ 开头，则下一段的开头应该在一个区间内，设其为 $[l_i,r_i]$。显然 $\forall j<i$ 都有 $l_j\le l_i,r_j\le r_i$，那么可以双指针求出 $l_i$ 和 $r_i$。

接下来可以从后往前扫，求出 $f_i$ 表示若某一段以 $i$ 开头的话，$b_{[i,n]}$ 能否完成合法的分段。

那么若 $f_1=0$ 就无解。

然后从前往后贪心，显然每一段肯定都是越长越好，所以每次贪心找到 $j\in [l_i,r_i],f_j=1$ 的最大的 $j$，分出段 $[i,j-1]$ 即可，注意这也相当于 $j\in[1,r_i]$，故做前缀最大值即可。

最后扫一遍即可求出答案，注意不在 $b$ 中出现的位置也要填数。

最后一段要特殊处理，时间复杂度 $O(n+m)$。

代码如下：

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>

using namespace std;

const int S=300005;

int n,m,a[S];
int ct[S];
int lb[S],rb[S];
bool flg[S];
int sm[S],mx[S];
bool vis[S];
int ans[S];

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	ct[a[1]]=1;
	lb[1]=2;
	for(int i=2,j=1;i<=m;i++)
	{
		ct[a[i-1]]--;
		while(j<=m&&ct[a[i-1]]==0) ct[a[++j]]++;
		if(j==m+1) lb[i]=-1;
		else lb[i]=j+1;
	}
	for(int i=1;i<=n;i++) ct[i]=0;
	ct[a[1]]=1;
	for(int i=1,j=1;i<=m;i++)
	{
		ct[a[i-1]]--;
		while(j<m&&ct[a[j+1]]==0) ct[a[++j]]++;
		rb[i]=j+1;
	}
	for(int i=1;i<=n;i++) ct[i]=0;
	int L=m;
	flg[m+1]=true;
	for(int i=m;i>=1;i--)
	{
		if(++ct[a[i]]==2) break;
		flg[i]=true;
		L=i;
	}
	sm[m+1]=1;
	for(int i=m;i>=1;i--)
	{
		if(lb[i]!=-1&&lb[i]<=rb[i])
			flg[i]|=(sm[lb[i]]-sm[rb[i]+1]>0);
		sm[i]=flg[i]+sm[i+1];
	}
	if(!flg[1]) return cout<<"-1\n",0;
	for(int i=1;i<=m;i++)
	{
		mx[i]=mx[i-1];
		if(flg[i]) mx[i]=i;
	}
	int p=1,t=0;
	while(p<L)
	{
		int np=mx[rb[p]];
		t++;
		for(int i=p;i<np;i++)
			if(!vis[a[i]]) ans[a[i]]=t,vis[a[i]]=true;
		p=np;
	}
	if(p<=m)
	{
		t++;
		for(int i=p;i<=m;i++)
			if(!vis[a[i]]) ans[a[i]]=t,vis[a[i]]=true;
	}
	for(int i=1;i<=n;i++) if(!vis[i]) ans[i]=t;
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';cout<<'\n';
	return 0;
}
/*
求出 i 为某一段开头时下一段开头所在的区间 [l_i,r_i]
那么 l[i] <= l[i+1]
	r[i] <= r[i+1]
然后我肯定想每一段长度构成的序列的字典序最大
那么处理出每一个点能不能到终点即可？
*/