题目描述

给定一个包含非零整数的数组 $a$。定义数组 $b$ 的 分数 为：数组 b 的长度 - 数组 b 中不同元素的数量。

你可以对数组 $a$ 最多执行一次 以下操作：
选择两个整数 $l$ 和 $r$ ($1 \le l \le r \le n$)。
从 $a$ 中移除连续子数组 $a[l \dots r]$。

你的目标是执行一次操作（或不执行操作），使得操作后得到的数组 $a’$ 的分数最大。

如果有多种操作都能得到最大分数，你需要选择使得操作后数组 $a’$ 长度最短 的那一种操作。如果仍然有多种选择，任意输出一种即可。

输出你选择的操作。如果不执行操作，输出 0。否则，输出选择的 $l$ 和 $r$。

样例

输入:
3
1
1
5
1 1 1 1 1
4
2 1 3 2

输出:
1 1
0
2 3

样例解释

• 样例 1: $a = [1]$。

  • 不操作：$a’ = [1]$。长度 1，不同元素 1。分数 = 1 - 1 = 0。长度 = 1。
  • 操作 $l=1, r=1$：移除 $[1]$。$a’ = []$ (空数组)。长度 0，不同元素 0。分数 = 0 - 0 = 0。长度 = 0。
    最大分数是 0。两种方案都达到最大分数。需要选择长度最短的方案，即操作 $l=1, r=1$。输出 1 1。

• 样例 2: $a = [1, 1, 1, 1, 1]$。

  • 不操作：$a’ = [1, 1, 1, 1, 1]$。长度 5，不同元素 1。分数 = 5 - 1 = 4。长度 = 5。
  • 操作 $l=1, r=1$：移除 $[1]$。$a’ = [1, 1, 1, 1]$。长度 4，不同元素 1。分数 = 4 - 1 = 3。长度 = 4。
  • 操作 $l=2, r=3$：移除 $[1, 1]$。$a’ = [1, 1, 1]$。长度 3，不同元素 1。分数 = 3 - 1 = 2。长度 = 3。
  • 操作 $l=1, r=5$：移除 $[1, 1, 1, 1, 1]$。$a’ = []$。长度 0，不同元素 0。分数 = 0 - 0 = 0。长度 = 0。
    最大分数是 4，通过不操作得到。输出 0。

• 样例 3: $a = [2, 1, 3, 2]$。

  • 不操作：$a’ = [2, 1, 3, 2]$。长度 4，不同元素 3 ($1, 2, 3$)。分数 = 4 - 3 = 1。长度 = 4。
  • 操作 $l=2, r=3$：移除 $[1, 3]$。$a’ = [2, 2]$。长度 2，不同元素 1 ($2$)。分数 = 2 - 1 = 1。长度 = 2。
  • 操作 $l=1, r=1$：移除 $[2]$。$a’ = [1, 3, 2]$。长度 3，不同元素 3。分数 = 3 - 3 = 0。长度 = 3。
  • 操作 $l=4, r=4$：移除 $[2]$。$a’ = [2, 1, 3]$。长度 3，不同元素 3。分数 = 3 - 3 = 0。长度 = 3。
  • 操作 $l=1, r=4$：移除 $[2, 1, 3, 2]$。$a’ = []$。长度 0，不同元素 0。分数 = 0 - 0 = 0。长度 = 0。
    最大分数是 1。有两种方案达到：不操作（长度 4）和操作 $l=2, r=3$（长度 2）。需要选择长度最短的方案，即操作 $l=2, r=3$。输出 2 3。

算法 (贪心 / 扫描)

$O(N)$

思路分析

1. 理解分数: 分数 = 长度 - 不同元素数。
   我们观察到，如果一个元素 $x$ 在数组中出现了 $k$ 次 ($k \ge 1$)，它对长度的贡献是 $k$，对不同元素数的贡献是 1。因此，这个元素 $x$ 对总分数的贡献是 $k - 1$。
   总分数可以看作是 $\sum_{x \in \text{distinct}(a’)} (\text{count}(x, a’) - 1)$，其中 $a’$ 是操作后的数组。

2. 最大化分数: 为了最大化分数，我们希望最终的数组 $a’$ 中，元素的重复度尽可能高，或者说，只出现一次的元素尽可能少。
   每个在最终数组 $a’$ 中只出现一次的元素，其对分数的贡献是 $1 - 1 = 0$。
   每个在最终数组 $a’$ 中出现 $k > 1$ 次的元素，其对分数的贡献是 $k - 1 > 0$。
   因此，对分数没有正贡献的是那些在最终数组里只出现一次的元素。

3. 操作的影响: 我们最多可以移除一个连续子数组 $a[l \dots r]$。移除操作会：

   • 减少数组的长度。
   • 可能减少不同元素的数量。
   • 可能改变某些元素的出现次数。

4. 关键观察: 考虑那些在原始数组 $a$ 中只出现一次的元素。设这样的元素集合为 $U$。

   • 如果一个元素 $x \in U$ 没有被移除（即它的原始位置不在 $l$ 到 $r$ 之间），那么它在最终数组 $a’$ 中也只会出现一次，对分数的贡献是 0。
   • 如果一个元素 $y \notin U$（即 $y$ 在原始数组中出现至少两次），即使移除操作减少了 $y$ 的出现次数，只要它在 $a’$ 中仍然出现至少一次，它对分数的贡献就是 $\ge 0$。如果它在 $a’$ 中出现次数仍然大于 1，它的贡献就是正的。如果移除操作使得 $y$ 在 $a’$ 中只出现一次，它的贡献就变成 0。如果移除操作使得 $y$ 在 $a’$ 中不再出现，它的贡献也变成 0。

5. 优化目标: 为了最大化分数，我们应该尽量保留那些在原始数组中出现多次的元素，并尽量移除那些在原始数组中只出现一次的元素。
   理想情况下，如果我们能通过移除一个连续子数组，使得剩下的数组 $a’$ 中不包含任何在原始数组 $a$ 中只出现一次的元素，那么这很可能是一个好的策略。
   为什么？因为原始数组中只出现一次的元素，无论如何操作（只要它没被移除），在最终数组里最多也只出现一次，对分数贡献为 0。移除它们不会降低潜在的最大分数。而原始数组中出现多次的元素，有可能对分数产生正贡献。

6. 最优策略: 寻找一个连续子数组 $a[l \dots r]$，这个子数组包含尽可能多的原始数组中只出现一次的元素，并且这个子数组本身只包含原始数组中只出现一次的元素。
   假设我们找到了这样的一个最长的连续子数组 $a[l \dots r]$，其中所有的元素 $a_i$ ($l \le i \le r$) 在原始数组 $a$ 中都只出现一次。

   • 如果我们移除这个子数组 $a[l \dots r]$，得到 $a’$。
   • $a’$ 的长度为 $n - (r - l + 1)$。
   • $a’$ 中不再包含 $a[l \dots r]$ 这些原本只出现一次的元素。$a’$ 只包含两部分：原始数组中出现多次的元素，以及原始数组中只出现一次但在区间 $[l, r]$ 之外的元素。
   • 计算 $a’$ 的分数 len(a') - distinct(a')。

7. 与不操作比较:

   • 不操作的分数是 len(a) - distinct(a)。
   • 移除只含唯一元素的最长子数组 $a[l \dots r]$ 后的分数是 len(a') - distinct(a')。
     根据题目要求，我们要在所有能达到最大分数的操作中，选择使最终数组长度最短的操作。
   • 移除元素总是会使长度变短（或不变，但题目要求移除非空子数组）。
   • 如果最大分数可以通过不操作达到，我们仍然需要检查是否有某个移除操作也能达到同样的最大分数，并且使得最终长度更短。

8. 重新思考目标: 我们需要找到一个操作（移除 $a[l \dots r]$ 或不移除）使得 len(a') - distinct(a') 最大，并且 len(a') 最小。
   考虑只包含“原始唯一元素”的连续子段。移除这样的子段似乎是有利的，因为它移除了“分数贡献为 0”的元素，可能使得最终数组中重复元素的比例更高，从而提高分数。同时，移除这样的子段会缩短数组长度。

9. 最终策略: 找到原始数组 $a$ 中，最长的连续子数组 $a[l \dots r]$，满足其中每个元素 $a_i$ ($l \le i \le r$) 在整个数组 $a$ 中只出现一次。

   • 如果不存在这样的非空子数组（即每个元素都至少出现两次，或者数组只有一个元素且出现一次），那么最优策略是不操作（因为移除任何元素都可能降低分数或保持分数不变但增加长度复杂度）。此时输出 0。
   • 如果找到了这样的最长子数组 $a[l \dots r]$，那么移除这个子数组就是最优的操作。因为：
     • 它移除了最多的“分数贡献为0”的元素。
     • 它最大化了移除的长度，从而在所有可能的操作中，如果能达到最大分数，它倾向于产生最短的最终数组。
     • 比较移除这个子段和不操作：如果移除后分数更高，或者分数相同但长度更短，则执行移除。如果移除后分数更低，则不操作。如果分数相同且长度更长，则不操作。但是，由于我们找的是最长的这种子段，移除它是在最大化分数目标下的最优“缩短长度”策略。因此，只要存在这样的非空子段，移除它总是比不移除（在满足题目条件下）更优或等优且长度更短。
     • 特例：如果原始数组本身就只有一个元素，移除它得到空数组，分数 0，长度 0。不移除，分数 0，长度 1。应移除。

10. 算法实现:
    a. 计算每个元素在数组 $a$ 中出现的频率 cnt。
    b. 遍历数组 $a$，找到最长的连续子段 a[l...r]，其中每个 a[i] 满足 cnt[a[i]] == 1。
    c. 记录这个最长子段的起始和结束索引 best_l, best_r 以及其长度 max_len。
    d. 如果 max_len == 0（即不存在这样的非空子段），输出 0。
    e. 否则，输出 best_l + 1 和 best_r + 1（转换为 1-based 索引）。

11. 代码解读:

    • vector<int> cnt(n): 存储频率，大小为 n 足够，因为题目说 $1 \le a_i \le n$。
    • 循环计算 cnt。
    • 变量 l, r 记录当前找到的最长“纯唯一元素”子段的边界（0-based，r 是开区间端点）。len 记录当前正在扫描的“纯唯一元素”子段的长度。
    • for (int i = 0; i < n; i++): 遍历数组。
      • if (cnt[a[i]] > 1): 如果当前元素不是唯一的，则中断当前子段，len = 0。
      • else { len++; }: 如果当前元素是唯一的，则延长当前子段。
      • if (len > r - l): 如果当前子段 len 比记录的最长子段 r - l 更长，则更新 r 和 l。r 更新为 i + 1 (当前位置之后)，l 更新为 r - len (子段的起始位置)。
    • if (l == r): 如果最终 l == r，说明最长子段的长度为 0，输出 0。
    • else: 输出 l + 1 和 r (将 0-based 的 l 和 0-based 开区间的 r 转换为 1-based 闭区间的 l 和 r)。

时间复杂度

• 计算频率 cnt: O(N)。
• 遍历数组寻找最长子段: O(N)。
• 总时间复杂度: O(N)。

空间复杂度

• 存储数组 a: O(N)。
• 存储频率 cnt: O(N)。
• 总空间复杂度: O(N)。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

// 定义常用类型别名 (在本题中仅 i64 可能在计数时有用，但 N 最大 2e5，int 足够)
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

// 解决单个测试用例的函数
void solve() {
    int n; // 数组长度
    std::cin >> n;

    std::vector<int> a(n); // 存储输入的数组 a
    // cnt[x] 存储元素 x+1 在数组 a 中出现的次数
    // 大小为 n 足够，因为 1 <= a[i] <= n
    std::vector<int> cnt(n); 
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i]--; // 转换为 0-based 索引 (元素值范围变为 0 到 n-1)
        cnt[a[i]]++; // 统计频率
    }

    int l = 0, r = 0; // 记录找到的最长“纯唯一元素”子段的边界 [l, r) (0-based, r 是开区间)
    int len = 0; // 当前扫描到的“纯唯一元素”子段的长度

    // 遍历数组 a
    for (int i = 0; i < n; i++) {
        // 检查当前元素 a[i] 是否是唯一的 (频率是否为 1)
        if (cnt[a[i]] > 1) {
            // 如果不是唯一的，则中断当前的“纯唯一元素”子段
            len = 0;
        } else {
            // 如果是唯一的，则延长当前子段
            len++;
        }

        // 如果当前子段的长度 len 大于记录的最长子段长度 r - l
        if (len > r - l) {
            // 更新最长子段的边界
            r = i + 1; // 结束边界 (开区间) 是当前位置 + 1
            l = i + 1 - len; // 起始边界 (闭区间)
        }
    }

    // 判断是否找到了非空的“纯唯一元素”子段
    if (l == r) { 
        // 如果 l == r，说明最长子段长度为 0，最优策略是不操作
        std::cout << 0 << "\n";
    } else {
        // 否则，找到了最长子段 [l, r)，输出其 1-based 的闭区间边界 [l+1, r]
        std::cout << l + 1 << " " << r << "\n";
    }
}

// 主函数
int main() {
    // 加速 IO
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t; // 测试用例数量
    std::cin >> t;

    // 处理每个测试用例
    while (t--) {
        solve(); // 调用解决函数
    }

    return 0; // 程序正常结束
}