题解 - Luogu P8986 [北大集训 2021] 基因编辑

简述题意

给定 $n,l,r(1<l\le r<n)$ 和长度为 $n$ 的正整数数列 $a(1\le a_i\le 10^6)$。一个数对 $(i,j)$ 合法，当且仅当：

• $1\le i<l\le r< j\le n$。
• 不存在 $i',j'$ 使得 $a_i=a_{i'}$，$a_j=a_{j'}$ 且 $i\neq i'\lor j\neq j'$。
• $a_i\neq a_j$。

找出可能的最小 $j-i+1$。$1\le n\le 10^6$。

分析

对于上面的第二个条件，我们这么转化：（可证明正确性）

• 不存在 $i'<j$，$i'\neq i$，$a_i=a_{i'}$。
• 不存在 $j'>i$，$j'\neq j$，$a_j=a_{j'}$。

它意味着：

• $j$ 在 $a_i$ 的头两次出现之间。
• $i$ 在 $a_j$ 的末两次出现之间。
• $i$ 是 $a_i$ 的第一次出现。
• $j$ 是 $a_j$ 的最后一次出现。

感性地理解，也就是这样的一对 $(a_i,a_j)=(x,y)$，分布形如 $\{y,\ldots,y,x,y,x,\ldots,x\}$。其中唯一的一组 $(x,y)$ 就是 $(i,j)$ 位了。

那么，我们枚举 $i<l$，只看所有末两次出现在 $i$ 两侧的 $a_j(j>r)$，然后检测这个条件下最小的 $j$ 是否在 $a_i$ 的头两次出现之间。而这里的 $j$ 可以逐个预处理，然后枚举的时候做一个前缀 $\min$。

时间、空间复杂度均为 $O(n)$。

代码

#include <bits/stdc++.h>
using namespace std;

const int MXN = 1000005;
int N, L, R, arr[MXN];
int fir[MXN], fir2[MXN], lst[MXN], lst2[MXN], mnr[MXN], cmr, ans;

int main() {
  cin >> N >> L >> R;
  for (int i(0); i != MXN; ++i) fir[i] = fir2[i] = N + 1;
  mnr[0] = N + 1;
  for (int i(1); i <= N; ++i) {
    cin >> arr[i];
    lst2[arr[i]] = lst[arr[i]];
    lst[arr[i]] = i;
    if (fir[arr[i]] == N + 1) fir[arr[i]] = i;
    else if (fir2[arr[i]] == N + 1) fir2[arr[i]] = i;
    mnr[i] = N + 1;
  }
  for (int i(R + 1); i <= N; ++i) {
    if (i == lst[arr[i]]) mnr[lst2[arr[i]]] = min(mnr[lst2[arr[i]]], i);
  }
  cmr = mnr[0];
  ans = N + 1;
  for (int i(1); i < L; ++i) {
    if (i == fir[arr[i]] && cmr < fir2[arr[i]]) ans = min(ans, cmr - i + 1);
    cmr = min(cmr, mnr[i]);
  }
  cout << (ans == N + 1 ? -1 : ans) << endl;
  return 0;
}