P13339 [EGOI 2025] Gift Boxes / 礼品盒

今年的 EGOI 在波恩举办。主办方希望为比赛中的每支队伍最多分发一个礼品盒，每支队伍的编号为 $0$ 到 $T-1$。所有参赛选手排成一排，但他们的顺序是混乱的，因此同一队的成员可能不会站在一起。注意，队伍中一定至少有一支队伍在队列中有多于一名成员。队列中共有 $N$ 个人，第 $i$ 个人属于编号为 $a_i$ 的队伍。问题是：每支队伍最多只能获得一个礼品盒。为了让礼品发放过程顺利进行——即使因此有些队伍无法获得礼品盒——主办方希望在发放过程中**恰好暂停一次**，跳过一段连续的选手，然后再继续发放。换句话说，他们会跳过一个连续区间 $[\ell, r]$ 的选手。 并不要求每支队伍都必须收到礼品盒。然而，主办方希望在不违反“每支队伍至多一个礼品盒”这一前提下，使收到礼品盒的队伍数尽量多，同时要**最小化被跳过的选手数量**。请帮助主办方决定在哪一段暂停以及何时继续发放礼品盒，才能使被跳过的选手尽可能少。

输入的第一行包含两个整数 $T$ 和 $N$——队伍数和队列中的选手数。 第二行包含 $N$ 个整数 $a_i$，第 $i$ 个整数表示队列中第 $i$ 个选手所属的队伍编号。保证 $0$ 到 $T-1$ 的每个整数至少出现一次。

输出两个整数 $\ell$ 和 $r$，分别表示被跳过的第一个和最后一个选手的下标。注意，$\ell$ 和 $r$ 的下标范围为 $0$ 到 $N-1$。如果有多个解，输出其中任意一个即可。

第一个样例满足测试组 1、3、5 和 6 的约束。有两种不同的输出：$1\ 1$（对应下划线蓝色线段）和 $4\ 4$（对应红色虚线），如图所示。无论哪种方式，四支队伍都能收到礼品盒，且没有队伍收到多于一个礼品盒。 $\begin{array}{lllll} 1 & \blue 3 & 0 & 2 & \red 3 \end{array}$ 第二个样例满足测试组 2、3、4、5 和 6 的约束。同样有两种不同的输出：$0\ 2$ 和 $3\ 5$，如图所示。两种方案下，三支队伍都能收到礼品盒。 $\begin{array}{lllll} \blue 1 & \blue 0 & \blue 2 & \red 2 & \red 1 & \red 0 \end{array}$ 第三个样例满足测试组 3、4、5、6 的约束。最优解是三支队伍收到礼品盒，如下所示。下标为 0、1、7 的选手（分别属于队伍 0、2、3）收到礼品盒。这是唯一的可行解。 $\begin{array}{lllllll} 0 & 2 & \blue 0 & \blue 1 & \blue 2 & \blue 1 & \blue 3 & 3 \end{array}$ 第四个样例满足测试组 3、5 和 6 的约束。同样有两种不同的输出：$0\ 3$ 和 $1\ 4$，如图所示。两种方案下，恰好两支队伍（队伍 0 和队伍 1）获得礼品盒。队伍 2 没有获得礼品盒，因为这样会导致队伍 0 或 1 获得两个礼品盒，这是严格禁止的。 $\begin{array}{lllllll} \blue 1 & \blue 1 & \blue 2 & \blue 0 & 1 & 0 \end{array}$ $\begin{array}{lllllll} 1 & \red 1 & \red 2 & \red 0 & \red 1 & 0 \end{array}$ 第五个样例满足测试组 3、5 和 6 的约束。唯一可行答案是 $2\ 3$，如图所示。所有四支队伍都能收到礼品盒。 $\begin{array}{lllllll} 0 & 1 & \blue 2 & \blue 0 & 3 & 2 \end{array}$ 第六个样例满足测试组 3、5 和 6 的约束。最多有五支队伍中的四支能收到礼品盒，如下所示。下标为 0、10、11 和 12 的选手（分别属于队伍 3、4、1、0）收到礼品盒。这是唯一的可行解。 $\begin{array}{lllllll} 3 & \blue 3 & \blue 3 & \blue 1 & \blue 2 & \blue 0 & \blue 3 & \blue 3 & \blue 2 & \blue 1 & 4 & 1 & 0 \end{array}$ ### 约束与评分 * $1 \leq T < N \leq 500\,000$ * $0 \leq a_i \leq T-1$ 你的解答将在一组测试组上进行评测，每组有若干测试用例。要获得该测试组的分数，你需要通过该测试组的所有测试用例。 | 测试组 | 分值 | 限制条件 | | :-: | :-: | :-: | | 1 | 8 | $N = T + 1$，即只有一支队伍会出现两次 | | 2 | 11 | $N = 2 \cdot T$，且每支队伍在前半部分和后半部分各出现一次 | | 3 | 14 | $1 \leq T < N \leq 500$ | | 4 | 21 | $N = 2 \cdot T$，且每支队伍均出现两次 | | 5 | 22 | $1 \leq T < N \leq 5\,000$ | | 6 | 24 | 无额外限制 | 翻译由 ChatGPT-4.1 完成。