自动搬运

查看原文

来自洛谷，原作者为

	O_Yeee "Let bygones be bygones. Focus on what you can do now."

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

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

以下是正文

题目非常冗长，但我们只需要关注这一段即可。

需要注意的是，在步骤 2 中，挑选的这对下标必须对应唯一的 noicleobase 组合。也就是说，能够满足 $s_{i'}=s_i, s_{j'} = s_j$ 且 $i<j$ 的有序对 $\left(i', j'\right)$ 必须是唯一的（即为 $(i,j)$），否则特异性识别工具可能切割下其它区段的基因序列；另外，$s_i\ne s_j$，否则特异性识别工具可能只切割下单个 noicleobase。

这句话告诉我们：对于题目所要找到的区间的左端点和右端点必须满足以下条件：

记：

$fir_{i}$ 为当前 $a_{i}$ 出现第一次的位置。

$las_{i}$ 为当前 $a_{i}$ 出现最后一次的位置。

而对于第一个（最后一个）来说，他们的 $fir_{i}$（$las_{i}$）是第一个与其相同的位置。

对于一个满足要求的区间$[l,r]$来说，一定要满足的条件是：

为什么呢，因为我们的定义说明在 $fir_{i}$ 之前是没有这个数字的，而在这里是第一个，遂满足题目的条件（$las_{i}$ 同理）。

因此我们定义 $head,tail$ 代表这个区间的头和尾，最开始分别是 $l-1,r+1$，每次判断 $fir_{head}>tail$ 和 $las_{head}<tail$。当满足条件时就是最短的区间，不满足则扩大，若到 $(head \leq 0) \land (tail>n)$ 仍未找到，就代表无解，输出 $-1$。

下面是代码。（可能求 $fir$ 和 $las$ 实现较复杂，仅供参考）

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,L,R;
int a[N],fir[N],before[N],las[N],after[N],bf[N],id[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> L >> R;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=1;i<=n;i++){
		if(before[a[i]]){
			fir[i]=before[a[i]];
		}
		else{
			before[a[i]]=i;
			fir[i]=i;
		}
	}
	for(int i=1;i<=n;i++){
		if(fir[i]==i){
			bf[a[i]]=1;
			id[a[i]]=i;
			continue;	
		}
		if(bf[a[i]]==1){
			fir[id[a[i]]]=i;
			bf[a[i]]=0;
		}
	}
	memset(bf,0,sizeof(bf));
	memset(id,0,sizeof(id));
	for(int i=n;i>=1;i--){
		if(after[a[i]]){
			las[i]=after[a[i]];
		}
		else{
			after[a[i]]=i;
			las[i]=i;
		}
	}
	for(int i=n;i>=1;i--){
		if(las[i]==i){
			bf[a[i]]=1;
			id[a[i]]=i;
			continue;	
		}
		if(bf[a[i]]==1){
			las[id[a[i]]]=i;
			bf[a[i]]=0;
		}
	}
	for(int i=1;i<=n;i++){
		if(fir[i]==i)fir[i]=n+1;
		if(las[i]==i)las[i]=-1;
	}
	int head=L-1,tail=R+1;
	while(head>0&&tail<=n){
		if((fir[head]>tail&&las[tail]<head)&&a[head]!=a[tail]){
			cout << tail-head+1;
			return 0;
		}
		if(fir[head]<tail)head--;
		if(las[tail]>head)tail++;
		if(a[head]==a[tail])head--,tail++;
		
	}
	cout << -1;
   return 0;
}

（本人第一次写题解，不喜勿喷，有问题欢迎在评论区讨论或私信作者。） （8.14修改第二次） （8.18修改第三次）