询问 a1,a2,⋯an 能否通过若干次将任意区间全部赋值为其中位数这个操作,来使得整个序列全部变为k。(中位数指第 ⌊2∣s∣+1⌋ 小的数)
多次询问,每次第一行两个整数 n 和 k,第二行 n 个整数 a1,a2,⋯an。
1≤n≤105,1≤k≤109,1≤ai≤109,并保证所有询问中n的和不超过 105。
首先如果 a 中没有 k 那么无解。
容易发现,若有连续两个 k,那么就可以不断向外拓展,一定有解。
否则考虑一次操作之后的结果:
- 长度为 2 的连续段:都变成较小的数
- 长度为 3 且有两个数相同的连续段:都变成相同的数
所以当某个 k 旁边有一个 ≥k 的数就一定有解。
那么考虑找到两个相邻且 ≥k 的数,把它们变成相同的数,然后不断向外拓展,直到遇到 ai=k 的位置。这样就可以造出两个相邻的 k,有解。
还有一种情况,若 ai 和 ai+2 都 ≥k 也可以变出相邻两个 ≥k 的数,否则就无解,因为 <k 的数不会比 ≥k 的数少。