联合省选 2025 游记

Day $(-\infin,-1]$

Day $0$

Day $1$ 上午

如何判定一个数 $x$ 能否成为中位数。

记 $x$ 的个数为 $cnt$，小于 $x$ 的个数为 $L$，大于 $x$ 的个数为 $R$。

考虑每个 $i$ 的决策：

1. $x \in [l_{i,2},r_{i,2}]$。不难发现此时选满 $x$ 是最优的，$cnt \larr cnt+ r_{i,2}$
2. $r_{i,2}<x$。此时我们并不关心选了什么，直接贡献到 $L$。
3. $l_{i,2}>x$。同理，贡献到 $R$。

将出现过的点排序，扫一遍同时动态维护 $cnt$，以及 $L,R$ 的取值范围。

$x$ 能成为中位数当且仅当：

$$\left\{ \begin{align} L< \lceil \frac{L+R+cnt+1}{2} \rceil \\ L+cnt \ge \lceil \frac{L+R+cnt+1}{2} \rceil \end{align} \right.$$

分讨 $L,R,cnt$ 奇偶性 $8$ 种情况把取上整拆掉，整理以后判断区间交是否为空即可。

看上去是操作分块，然而怎么操作分块呢？

写了个究极乱搞+暴力，跑路。

树的部分分看起来可做。

一颗子树对应到 $p$ 的逆排列上是一个区间。要求字典序最小，然后贪心（？）

时间不太够了啊。

Day $1$ 下午

Day2 上午

Day2 下午