#5730. 「NOISG 2026 Final」3 Raptors

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

译自 NOISG 2026 Final T3. 3 Raptors

WhiteRaptor 终于在猛禽之地（TheRaptorLand）找到了自己的同类！与单调的 WhiteRaptor 不同，猛禽之地生活着各种颜色的猛禽：粉猛禽（PinkRaptor）、蓝猛禽（BlueRaptor）和绿猛禽（GreenRaptor）。

WhiteRaptor 将猛禽之地的所有 $n$ 只猛禽排成一列，从左到右编号为 $1$ 到 $n$。从左侧起第 $i$ 只猛禽的颜色为 $c[i]$。他想挑选一些猛禽永远留在他的地下室里陪伴他。然而，他只能通过从队伍的左端和右端分别移除零只或多只猛禽，并保留剩下的所有猛禽（即保留原队列中一段连续的区间）来实现这一目标。

为了确保留下的猛禽中没有谁会受到排挤，他希望出现频率最高的猛禽颜色与出现频率最低的猛禽颜色之间的差值不超过 $k$。需要注意的是，若留下的猛禽中不存在某种颜色的猛禽，则该颜色的出现频率计为 $0$。

请帮助 WhiteRaptor 找到他最多能保留多少只猛禽！

输入格式

第一行包含两个整数 $n$ 和 $k$。

第二行包含 $n$ 个由空格分隔的整数 $c[1], c[2], \ldots, c[n]$。

输出格式

输出一个整数，表示他最多能保留的猛禽数量。

样例 1

输入

11 2
2 2 1 2 1 3 2 1 2 1 1

输出

7

从第 $3$ 只猛禽到第 $9$ 只猛禽，颜色 $c[i]=1, 2, 3$ 的猛禽数量分别为 $3, 3, 1$。由于最大频率与最小频率之差未超过 $k=2$，这组猛禽满足 WhiteRaptor 的标准。

一个不符合标准的猛禽集合例子是从第 $3$ 只猛禽到第 $10$ 只猛禽，因为增加了一只颜色 $c[i]=1$ 的猛禽，使得出现频率最高的颜色频率变为 $4$。导致最大频率与最小频率之差为 $3$，超过了 $k=2$。

可以证明，$7$ 是 WhiteRaptor 在满足标准的前提下能保留的猛禽最大数量。

此样例满足子任务 $1,2,6$ 和 $7$ 的限制。

样例 2

输入

6 2
2 1 3 3 3 3

输出

5

WhiteRaptor 应该选择从第 $1$ 只到第 $5$ 只的猛禽。

此样例满足子任务 $1,2,5$ 和 $7$ 的限制。

样例 3

输入

7 0
1 2 1 2 1 2 1

输出

0

由于任何连续的猛禽序列中都不包含颜色 $c[i]=3$ 的猛禽，因此出现频率最低的颜色频率将始终为 $0$。这意味着 WhiteRaptor 无法选择任何非空的猛禽序列。因此，输出为 $0$。

请注意，此测试用例满足子任务 $5$，因为我们可以令 $j=n$（即不出现颜色为 $3$ 的猛禽）。

此样例满足所有子任务的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 200000$
• $0 \leq k \leq 200000$
• 对于所有 $1 \leq i \leq n$，$1 \leq c[i] \leq 3$

详细子任务附加限制及分值如下表所示：