众数 I - 算法题解 - pigstd 的 std::deque - C++ 实现

众数 I - 算法题解 - pigstd 的 std::deque - C++ 实现/n/n题目背景/n/npigstd 是一个可爱的男孩子。他在 NOI2022 中的众数一题定义了 //$10^6//$ 个 std::deque 并没有 MLE。/n/n题目描述/n/n给定一个长度为 //$n//$ 的序列 //$a//$，我们通过以下方式构造序列 //$b//$：/n/n- 初始时 //$b=a//$。/n- 依次对 //$b//$ 进行 //$k//$ 次操作，每次操作选择任意一个元素并将其修改为任意整数。/n/ndXqwq 定义一个序列的众数为所有出现次数最大的数。例如 //$[1,1,4,5,1,4]//$ 的众数为 //$1//$，而 //$[1,14,5,14,19,19,8,10]//$ 的众数为 //$14,19//$。/n/n你需要求出有多少整数可能成为 //$b//$ 的众数。/n/n输入格式/n/n第一行输入两个整数 //$n,k//$。/n/n第二行输入 //$n//$ 个整数 //$a_i//$。/n/n输出格式/n/n输出一个整数，代表可能成为众数的数的数量。/n/n特别地，如果答案为正无穷，输出 pigstd。/n/n样例 #1/n/n### 样例输入 #1/n/n/n5 0/n1 2 3 4 5/n/n/n### 样例输出 #1/n/n/n5/n/n/n## 样例 #2/n/n### 样例输入 #2/n/n/n5 1/n1 2 3 4 5/n/n/n### 样例输出 #2/n/n/npigstd/n/n/n## 样例 #3/n/n### 样例输入 #3/n/n/n5 1/n1 1 2 2 3/n/n/n### 样例输出 #3/n/n/n3/n/n/n## 提示/n/n**【样例解释】/n/n对于第一组数据，最终 //$1,2,3,4,5//$ 可能为区间众数。/n/n对于第二组数据，将第一个数换成 //$6,7,8,9,/cdots//$ 后它们均会成为区间众数，因此答案为正无穷。/n/n对于第三组数据，//$1,2,3//$ 可能成为区间众数。/n/n【提示】/n/n开 //$10^6//$ 个 std::deque 在空间限制为 1024MB 时不一定会 MLE。/n/n【数据范围】/n/n本题采用捆绑测试。/n/n* Subtask 1（20 pts）：//$n//leq 5//$。/n* Subtask 2（20 pts）：//$n//leq 10^3//$。/n* Subtask 3（20 pts）：//$k=0//$。/n* Subtask 4（20 pts）：//$k=1//$。/n* Subtask 5（20 pts）：无特殊限制。/n/n对于 //$100//%$//$ 的数据，//$1//leq n//leq 10^6//$，//$0//leq k//leq n $，//$1//leq a_i//leq n//$。/n用C++做，不要用unordered_map和auto内容：测试点1 /n/n//$n=k=5//$，//$a=[1,2,3,4,5]//$/n/n所有的数都只出现一次，所以每个数都有//$n=5//$种可能成为众数的情况。/n/n测试点2** /n/n//$n=k=5//$，//$a=[1,1,1,1,1]//$/n/n所有的数都相同，所以只有一个数可以成为众数。/n/n测试点3 /n/n//$n=k=5//$，//$a=[1,1,2,2,3]//$/n/n只有1、2、3可以成为众数。/n/n测试点4 /n/n//$n=k=5//$，//$a=[1,1,1,1,2]//$/n/n只有1可以成为众数。/n/n测试点5 /n/n//$n=k=1//$，//$a=[1]//$/n/n只有1可以成为众数。/n/n测试点6 /n/n//$n=k=1//$，//$a=[1000000]//$/n/n只有一个数，所以只有它自己可以成为众数。/n/n测试点7 /n/n//$n=k=10^3//$，//$a=[1,2,3,/cdots,1000]//$/n/n所有的数都只出现一次，所以每个数都有//$n=1000//$种可能成为众数的情况。/n/n测试点8 /n/n//$n=k=10^3//$，//$a=[1,1,1,/cdots,1]//$/n/n所有的数都相同，所以只有一个数可以成为众数。/n/n测试点9 /n/n//$n=k=10^3//$，//$a=[1,1,2,2,3,3,/cdots,1000,1000]//$/n/n只有1、2、3可以成为众数。/n/n测试点10 /n/n//$n=k=10^3//$，//$a=[1,1,1,1,2,2,/cdots,999,999,1000]//$/n/n只有1和2可以成为众数。/n/n测试点11 /n/n//$n=k=10^6//$，//$a=[1,2,3,/cdots,1000000]//$/n/n所有的数都只出现一次，所以每个数都有//$n=1000000//$种可能成为众数的情况。/n/n测试点12 /n/n//$n=k=10^6//$，//$a=[1,1,1,/cdots,1]//$/n/n所有的数都相同，所以只有一个数可以成为众数。/n/n测试点13 /n/n//$n=k=10^6//$，//$a=[1,1,2,2,3,3,/cdots,999999,999999,1000000]//$/n/n只有1、2、3可以成为众数。/n/n测试点14 /n/n//$n=k=10^6//$，//$a=[1,1,1,1,2,2,/cdots,999998,999998,999999,999999,1000000]//$/n/n只有1和2可以成为众数。/n