CF1349B Orac and Medians 做题记录

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

多次询问,每次第一行两个整数 nnkk,第二行 nn 个整数 a1,a2,ana_1,a_2,\cdots a_n

1n105,1k109,1ai1091 \le n \le 10^5,1 \le k \le 10^9,1 \le a_i \le 10^9,并保证所有询问中nn的和不超过 10510^5

首先如果 aa 中没有 kk 那么无解。

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

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

  1. 长度为 22 的连续段:都变成较小的数
  2. 长度为 33 且有两个数相同的连续段:都变成相同的数

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

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

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