题解：P8986 [北大集训 2021] 基因编辑
O_Yeee
·
·
题解
题目非常冗长，但我们只需要关注这一段即可。
需要注意的是，在步骤 2 中，挑选的这对下标必须对应唯一的 noicleobase 组合。也就是说，能够满足 s_{i'}=s_i, s_{j'} = s_j 且 i<j 的有序对 \left(i', j'\right) 必须是唯一的（即为 (i,j)），否则特异性识别工具可能切割下其它区段的基因序列；另外，s_i\ne s_j，否则特异性识别工具可能只切割下单个 noicleobase。
这句话告诉我们：对于题目所要找到的区间的左端点和右端点必须满足以下条件：
记：
$las_{i}$ 为当前 $a_{i}$ 出现最后一次的位置。
而对于第一个（最后一个）来说，他们的 $fir_{i}$（$las_{i}$）是第一个与其相同的位置。
对于一个满足要求的区间$[l,r]$来说，一定要满足的条件是：
$$
(fir_{l}>r) \land (las_{r}<l)
$$
为什么呢，因为我们的定义说明在 $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$ 实现较复杂，仅供参考）
```cpp
#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修改第三次）