题目概述

有 $N$ 个人排成一队，属于 $T$ 个不同的团队。组织者要给队伍分发礼品盒，但每个团队最多只能收到一个礼品盒。为了满足这个条件，组织者可以选择跳过一段连续的区间 $[\ell, r]$ 不发礼品。

目标：在确保没有团队收到超过一个礼品的前提下，最小化跳过的区间长度（即 $r-\ell+1$ 最小）。

问题分析

核心矛盾

如果某个团队在队列中出现了多次，那么直接从头到尾发礼品就会导致该团队收到多个礼品，违反规则。

关键观察

1. 必须跳过的部分：

   • 对于每个团队，如果它在队列中出现多次，那么我们必须跳过其中一些出现位置
   • 但我们可以通过跳过一段连续区间来同时解决多个团队的重复问题

2. 问题转化：

   • 我们要找到一个最短的连续区间 $[\ell, r]$，使得在移除这个区间后，剩下的前缀和后缀中，每个团队最多出现一次
   • 换句话说：前缀 $[0, \ell-1]$ 和后缀 $[r+1, N-1]$ 中都没有重复的团队

算法思路

步骤1：确定必须跳过的范围

1. 从左往右扫描找到第一个出现重复团队的位置 $st$：

   • 在 $[0, st-1]$ 中所有团队最多出现一次
   • 位置 $st$ 是某个团队第二次出现的位置

2. 从右往左扫描找到第一个出现重复团队的位置 $en$：

   • 在 $[en+1, N-1]$ 中所有团队最多出现一次
   • 位置 $en$ 是某个团队从右往左第二次出现的位置

步骤2：滑动窗口寻找最优解

现在我们知道，跳过的区间必须包含 $[st, en]$ 中的某些部分。具体来说：

• 跳过的区间 $[L, R]$ 必须满足：
  • $L \le st$（因为前缀 $[0, L-1]$ 不能有重复）
  • $R \ge en$（因为后缀 $[R+1, N-1]$ 不能有重复）

使用滑动窗口方法：

• 初始窗口：$[L, R] = [1, en]$（1-based索引）
• 不断右移 $L$，同时调整 $R$ 确保窗口仍然有效
• 记录长度最小的窗口

算法详解

步骤1代码解析

// 从左往右找第一个重复
for (int i = 1; i <= n; i++)
    if (++hsh_l[a[i]] == 2) {
        st = i;  // 第一个重复位置
        hsh_l[a[i]]--;
        break;
    }

// 从右往左找第一个重复  
for (int i = n; i; i--)
    if (++hsh_r[a[i]] == 2) {
        en = i;  // 从右往左第一个重复位置
        hsh_r[a[i]]--;
        break;
    }

步骤2代码解析

int L = 1, R = en;
while (L <= st) {
    // 更新最优解
    if (R - L + 1 < len)
        len = R - L + 1, ansl = L, ansr = R;
    
    // 右移L时，可能需要右移R来保持有效性
    while (R <= n && hsh_r[a[L]] == 1)
        hsh_r[a[++R]]--;
    
    if (R > n) break;
    
    hsh_r[a[L++]]++;
}

滑动窗口的维护：

• 当左指针 $L$ 右移时，$a[L]$ 被加入后缀部分
• 如果 $a[L]$ 在后缀中已经存在（hsh_r[a[L]] == 1），就需要右移 $R$ 来排除这个重复
• 保持后缀 $[R+1, N]$ 中没有重复团队

样例分析

样例1

输入：4 5
      1 3 0 2 3
处理：
- 从左扫描：位置1(团队1) → 位置2(团队3) → 位置3(团队0) → 位置4(团队2) → 位置5(团队3)重复！st=5
- 从右扫描：位置5(团队3) → 位置4(团队2) → 位置3(团队0) → 位置2(团队3)重复！en=2
- 滑动窗口：初始[1,2]，最终找到[2,2]（输出1,1）

样例2

输入：3 6  
      1 0 2 2 1 0
处理：
- 从左：位置3(团队2)重复，st=3
- 从右：位置4(团队1)重复，en=3  
- 滑动窗口找到[1,3]（输出0,2）

正确性证明

为什么这样能找到最优解？

1. 必要性：任何有效的跳过区间必须包含 $[st, en]$ 中的某些部分，否则前缀或后缀中会有重复
2. 充分性：滑动窗口保证找到的区间移除后，前缀和后缀都没有重复
3. 最优性：窗口从左到右扫描，总是维护当前最短的有效区间

时间复杂度

• 两次线性扫描：$O(N)$
• 滑动窗口：每个元素最多进出一次，$O(N)$
• 总复杂度：$O(N)$，满足 $N \le 500000$ 的要求

总结

这道题的关键在于：

1. 问题转化：将"每个团队最多一个礼品"转化为"前缀和后缀无重复"
2. 确定边界：通过左右扫描找到必须包含的区间 $[st, en]$
3. 滑动窗口：在约束条件下寻找最短跳过区间

这种"确定边界 + 滑动窗口"的思路，在解决需要满足前后缀条件的区间问题时非常有效。