自动搬运

查看原文

来自洛谷，原作者为

	ZGS_WZY **

搬运于2025-08-24 21:50:16，当前版本为作者最后更新于2021-10-03 11:50:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

额外提供一个LOJ的翻译

题目分析

我们考虑枚举每一个可能的相遇位置 $i$（即满足 $c[i]=x[m]=y[l]$ )，我们希望两个人所访问的第一个方格尽可能地靠近 $i$，分别记为 $x$,$y$，然后我们检查 $\left[1,x-1 \right]$ 和 $\left[y+1,n \right]$ 两个区间有没有相同的颜色即可。

因此题解分为以下两个部分：

$Part 1:$

$L[i]:$ 相遇点为 $i$ 时，第一个人下标最大的出发点。

$R[i]:$ 相遇点为 $i$ 时，第二个人下标最小的出发点。

实际上将颜色数组 $c$ 倒叙后求 $R[i]$ 的过程与求 $L[i]$ 的基本一样，所以这里只讨论 $L[i]$ 的求法。

我们可以维护若干个序列，表示从不同的起始点 $i$（即满足 $c[i]=a[1]$）出发经过的最长的下标序列，使得这些下标上对应的颜色能匹配 $a$ 数组的前若干位。而我们想要知道的就是长度为 $m$ 的上述序列中第一个下标最大是多少。

例如对于以下情况：

c:4 7 4 3 4 7 1 3 1
a:4 7 3 1
m=4

截止到第7个位置时，几个序列如下：

1 2 4 7
3 6
5 6

所以 $L[7]=1$。

直接维护效率过低，我们考虑优化。

$Hint 1:$

如果有两个序列长度一样，那我们可以直接舍弃掉前一个序列，因为它的第一位下标比后一个小，且它们两在往后匹配的过程中遇到的情况始终是一样的。（上面例子的第2,3两个序列就是如此）

$Hint 2:$

我们只需要知道每个序列第一个下标是多少，以及目前需要匹配 $a$ 数组中的第几位即可。

有了这两个想法，我们可以记 $pos[i]$ 表示需要匹配第 $i$ 个位置的序列编号。假设当前的 $c[i]=a[x]$ ，那么第 $pos[x]$ 个序列已经可以匹配第 $x$ 个位置，所以我们可以令 $pos[x+1]=pos[x]$。

可是如果在这之前有序列要匹配第 $x+1$ 个位置被覆盖了怎么办？没关系，因为根据第一个想法就算有，它也可以被舍弃了，此外这个优化还保证了每一个序列想要匹配的位置一定不一样。

附上代码：

for(int i=1;i<=m;i++)num[a[i]]=i;
pos[1]=1;//造一个空序列需要匹配第一位
int tot=1;
for(int i=1;i<=n;i++){
	if(pos[num[c[i]]]){//存在一个序列需要匹配这一位
		int x=num[c[i]];
		if(x==1)H[pos[1]]=i;//记下出发点
		pos[x+1]=pos[x];pos[x]=0;
		if(x==1)pos[1]=++tot;//跟前面同理
	}
	L[i]=(pos[m+1]!=0&&c[i]==a[m])?H[pos[m+1]]:0;//如果有序列已经匹配完m位，L[i]即为那个序列的出发点。
}
//以下是求R[i]
memset(num,0,sizeof(num));memset(pos,0,sizeof(pos));memset(H,0,sizeof(H));
for(int i=1;i<=l;i++)num[b[i]]=i;
pos[1]=1;tot=1;
for(int i=n;i>=1;i--){
	if(pos[num[c[i]]]){
		int x=num[c[i]];
		if(x==1)H[pos[1]]=i;
		pos[x+1]=pos[x];pos[x]=0;
		if(x==1)pos[1]=++tot;
	}
	R[i]=(pos[l+1]!=0&&c[i]==b[l])?H[pos[l+1]]:n+1;
}

时间复杂度: $O(n)$

$Part 2:$

对于每一种颜色 $x$，我们可以求出它出现的最靠后的位置在哪儿，记为 $pos[x]$ (为了省空间用了同一个数组)。

然后对于位置 $i$，我们可以预处理一个前缀最大值 $pre[i]=\max \limits_{1\leq j \leq i}pos[c[j]]$。于是 $pre[i]$ 就可以表示区间 $\left [1,i\right]$中的颜色出现的最靠后的位置，如果 $pre[i] \geq r$，那么我们就可以认为区间 $\left [1,i\right]$ 和区间 $\left [r,n\right]$ 中有一样的颜色。

附上代码：

for(int i=1;i<=n;i++)pos[c[i]]=i;
for(int i=1;i<=n;i++)pre[i]=max(pre[i-1],pos[c[i]]);
for(int i=1;i<=n;i++){
	if(c[i]!=a[m])continue;
	if(pre[L[i]-1]>R[i])ans.push_back(i);
}

时间复杂度：$O(n)$