题目分析

给定序列 $s_1, s_2, \dots, s_n$ 和编辑区间 $[l, r]$，需要找到一对 $(i, j)$ 满足：

1. $1 \le i < l$ 且 $r < j \le n$
2. $(s_i, s_j)$ 在整个序列中唯一出现
3. $s_i \neq s_j$
4. 最小化 $j - i + 1$

---

核心思路

1. 唯一性条件分析

对于数值 $x$，定义其在序列中的"安全区间"：

• 左安全区间 $[ll_x, rr_x]$：$x$ 作为左端点时，右端点的有效范围
• 右安全区间 $[ll_y, rr_y]$：$y$ 作为右端点时，左端点的有效范围

$(s_i, s_j)$ 唯一当且仅当：

• $j \in [ll_{s_i}, rr_{s_i}]$
• $i \in [ll_{s_j}, rr_{s_j}]$
• $s_i \neq s_j$

2. 安全区间计算

左安全区间（对于 $i < l$ 的数值）：

for (int i = 1; i <= n; i++) {
    cnt[s[i]]++;
    if (cnt[s[i]] == 1 && i < l) {
        lc[s[i]].pos = i;      // 记录候选位置
        lc[s[i]].ll = i + 1;   // 安全区间左端点
    } else if (cnt[s[i]] == 2) {
        lc[s[i]].rr = i - 1;   // 安全区间右端点
    }
}
// 处理只出现一次的情况
for (int i = 1; i <= n; i++) {
    if (lc[s[i]].rr == 0)
        lc[s[i]].rr = n;
}

右安全区间（对于 $j > r$ 的数值）：

类似处理，但从右往左扫描。

---

算法实现详解

1. 数据结构设计

struct col {
    int pos, ll, rr;  // 候选位置, 安全区间左右端点
};
col lc[1000005], rc[1000005];  // 左右候选信息

2. 预处理阶段

左候选预处理

• 扫描 $1 \to n$，记录每个数值第一次出现在 $[1, l-1]$ 的位置
• 当数值第二次出现时，确定其安全区间的右边界
• 对于只出现一次的数值，安全区间延伸到序列末尾

右候选预处理

• 扫描 $n \to 1$，记录每个数值第一次出现在 $[r+1, n]$ 的位置
• 当数值第二次出现时，确定其安全区间的左边界
• 对于只出现一次的数值，安全区间延伸到序列开头

3. 双指针搜索

int lp = l - 1, rp = r + 1;

// 找到有效的左右候选
while (lp >= 1 && lc[s[lp]].pos != lp) lp--;
while (rp <= n && rc[s[rp]].pos != rp) rp++;

// 双指针搜索最优解
while (lp >= 1 && rp <= n) {
    if (满足安全区间条件 && s[lp] != s[rp]) {
        printf("%d", rp - lp + 1);
        return 0;
    }
    // 调整指针...
}

4. 条件检查

对于候选对 $(lp, rp)$，检查：

(lc[s[lp]].ll <= rp) && (lc[s[lp]].rr >= rp) &&  // rp在lp的安全区间内
(rc[s[rp]].ll <= lp) && (rc[s[rp]].rr >= lp) &&  // lp在rp的安全区间内  
s[lp] != s[rp]                                    // 数值不同

---

关键优化

1. 候选过滤

while (lp >= 1 && lc[s[lp]].pos != lp) lp--;
while (rp <= n && rc[s[rp]].pos != rp) rp++;

只考虑真正有效的候选位置。

2. 指针调整策略

• 当 $(lp, rp)$ 不满足条件时，优先移动 $lp$
• 移动 $lp$ 后，相应调整 $rp$ 到有效位置：

  while (rp <= n && rc[s[rp]].ll > lp) rp++;
  

3. 提前检查

else if (rp + 1 <= n && ... && s[lp] != s[rp + 1]) {
    printf("%d", rp + 1 - lp + 1);
    return 0;
}

检查 $rp+1$ 是否构成更优解。

---

复杂度分析

• 预处理：$O(n)$，两次线性扫描
• 双指针搜索：$O(n)$，每个位置最多被访问一次
• 总复杂度：$O(n)$，适合 $n \leq 10^6$ 的数据范围

---

算法标签

主要算法：

• 双指针
• 预处理优化
• 安全区间分析

相关技术：

• 唯一性判断
• 候选过滤
• 边界处理

---

代码亮点

1. 安全区间概念：将复杂的唯一性条件转化为区间包含关系
2. 双向预处理：分别从左右扫描，高效计算安全区间
3. 双指针优化：在候选对中线性搜索最优解
4. 提前终止：找到第一个可行解立即输出（由于搜索顺序保证最优）

---

总结

这道题通过安全区间分析和双指针搜索的巧妙结合，将复杂的唯一性判断问题转化为简单的区间包含检查。算法在线性时间内解决了大规模数据的最优解搜索问题，体现了对问题本质的深刻理解和高效算法的设计能力。