CF1349B Orac and Medians 做题记录

询问 $a_1,a_2,\cdots a_n$ 能否通过若干次将任意区间全部赋值为其中位数这个操作，来使得整个序列全部变为$k$。（中位数指第 $\lfloor \frac {∣s∣+1} 2 \rfloor$ 小的数）

多次询问，每次第一行两个整数 $n$ 和 $k$，第二行 $n$ 个整数 $a_1,a_2,\cdots a_n$。

$1 \le n \le 10^5,1 \le k \le 10^9,1 \le a_i \le 10^9$，并保证所有询问中$n$的和不超过 $10^5$。

首先如果 $a$ 中没有 $k$ 那么无解。

容易发现，若有连续两个 $k$，那么就可以不断向外拓展，一定有解。

否则考虑一次操作之后的结果：

1. 长度为 $2$ 的连续段：都变成较小的数
2. 长度为 $3$ 且有两个数相同的连续段：都变成相同的数

所以当某个 $k$ 旁边有一个 $\ge k$ 的数就一定有解。

那么考虑找到两个相邻且 $\ge k$ 的数，把它们变成相同的数，然后不断向外拓展，直到遇到 $a_i=k$ 的位置。这样就可以造出两个相邻的 $k$，有解。

还有一种情况，若 $a_i$ 和 $a_{i+2}$ 都 $\ge k$ 也可以变出相邻两个 $\ge k$ 的数，否则就无解，因为 $<k$ 的数不会比 $\ge k$ 的数少。