题解：P11830 [省选联考 2025] 幸运数字（民间数据）

· · 题解

题目传送门

这都能蓝，我觉得是绿诶。

\mathtt{Solution}

原问题不是很好考虑，那么我们先进行转化：给定一个 x，求 x 是否能成为中位数。

不难发现所有的区间 [l_{i,2},r_{i,2}] 就被分成了三类：严格在 x 左边的，包含 x 的，以及在 x 右侧的。

假设 x 左边最多有 M_1 个数，最少有 N_1 个数。

同理假设 x 右边/中间最多有 M_2,M_3 个数，最少有 N_2,N_3 个数。

接下来分类讨论：

  3. 如果都不满足，那么此时只需要把包含 x 的区间全部填成 x 即可。因为可以把左右两边的数量调整成相等的，所以即 x 可以成为中位数。

考虑了以上问题之后，你可以过 \mathtt{A} 性质，预计 60 分。

接下来思考如何把若干个 x 一起考虑。

先对 l_{i,2},r_{i,2} 离散化后，我们发现一段不包含 l_{i,2},r_{i,2} 的区间里面的 x 都是等价的。

后面排序离散化就行了，代码后面补。