考点：二分

数据规模 m ≤ 1e6 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 数据规模：m ≤ 1e6
• 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：二分

本题切入点

x 越大越容易满足条件，具备单调性；二分 x，check 时统计每种颜色的最大间隔是否都小于 x。

把「求最优值」转化为「判定某值是否可行」，用单调性二分逼近答案。

思路框架（二分 通法 · 非本题专属）

1. 确认单调性：答案越大/越小，条件越容易（或越难）满足。
2. 写出 check(x)：判断值为 x 时是否可行。
3. 在答案区间 [lo, hi] 上二分，每次取 mid 调 check，收缩区间。
4. 边界收敛到唯一答案，注意取整方向（求最小可行值用上取整）。

实现要点：模板：while (lo < hi) { mid = (lo+hi)/2; if (check(mid)) hi = mid; else lo = mid+1; } 求最小可行值。

复杂度：时间 O(check 的代价 × log(答案范围)) ｜ 空间 O(1)

该范式的通法易错点

• check 函数不满足单调性却硬套二分（会得到错误答案）。
• 二分边界或取整方向写错，陷入死循环或漏掉边界答案。

对照本题

• 数据规模 m ≤ 1e6，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。

样例解读

样例 1：输入 4 2 / 1 2 1 2 → 输出 2 1

当 x=4 时，满足的区间只有一个 [1,4] ，此时同时出现在这些区间里面的袜子颜色为 1 和 2 。

当 x=3 时，满足的区间为 [1,3] 和 [2,4] ，此时同时出现在这些区间里面的袜子颜色为 1 和 2 。

当 x=2 时，满足的区间为 [1,2] 、 [2,3] 和 [3,4] ，此时同时出现在这些区间里面的袜子颜色为 1 和 2 。

当 x=1 时，满足的区间为 [1,1] 、 [2,2] 、 [3,3] 和 [4,4] ，此时没有同时出现在这些区间里面的袜子颜色。