Orac and Medians
Contest: Codeforces Round 641 (Div. 1)
Difficulty rating: 2000
Tags: constructive algorithms, greedy, math

Slime has a sequence of positive integers $$$a_1, a_2, \ldots, a_n$$$.

In one operation Orac can choose an arbitrary subsegment $$$[l \ldots r]$$$ of this sequence and replace all values $$$a_l, a_{l + 1}, \ldots, a_r$$$ to the value of median of $$$\{a_l, a_{l + 1}, \ldots, a_r\}$$$.

In this problem, for the integer multiset $$$s$$$, the median of $$$s$$$ is equal to the $$$\lfloor \frac{|s|+1}{2}\rfloor$$$-th smallest number in it. For example, the median of $$$\{1,4,4,6,5\}$$$ is $$$4$$$, and the median of $$$\{1,7,5,8\}$$$ is $$$5$$$.

Slime wants Orac to make $$$a_1 = a_2 = \ldots = a_n = k$$$ using these operations.

Orac thinks that it is impossible, and he does not want to waste his time, so he decided to ask you if it is possible to satisfy the Slime's requirement, he may ask you these questions several times.

Input format:
The first line of the input is a single integer $$$t$$$: the number of queries.

The first line of each query contains two integers $$$n\ (1\le n\le 100\,000)$$$ and $$$k\ (1\le k\le 10^9)$$$, the second line contains $$$n$$$ positive integers $$$a_1,a_2,\dots,a_n\ (1\le a_i\le 10^9)$$$

The total sum of $$$n$$$ is at most $$$100\,000$$$.

Output format:
The output should contain $$$t$$$ lines. The $$$i$$$-th line should be equal to 'yes' if it is possible to make all integers $$$k$$$ in some number of operations or 'no', otherwise. You can print each letter in lowercase or uppercase.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first query, Orac can't turn all elements into $$$3$$$.

In the second query, $$$a_1=6$$$ is already satisfied.

In the third query, Orac can select the complete array and turn all elements into $$$2$$$.

In the fourth query, Orac can't turn all elements into $$$3$$$.

In the fifth query, Orac can select $$$[1,6]$$$ at first and then select $$$[2,10]$$$.

Example input:
5
5 3
1 5 2 6 1
1 6
6
3 2
1 2 3
4 3
3 1 2 3
10 3
1 2 3 4 5 6 7 8 9 10

Example output:
no
yes
yes
no
yes

Editorial:
Let $$$B_i=\left\{\begin{aligned} 0,A_i<k\\1,A_i=k\\2,A_i>k\end{aligned} \right.$$$，then just consider whether it can be done to make all elements in $$$B$$$ become $$$1$$$ in a finite number of operations.
It can be proved that a solution exists if and only if $$$\exists 1\le i\le n,\mathrm{s.t.}B_i=1$$$ and $$$\exists 1\le i<j\le n,\mathrm{s.t.}j-i\le2,B_i>0,B_j>0$$$ .
The necessity is obvious: if $$$\forall 1\le i\le n, B_i\neq 1$$$ , no elements in $$$B$$$ can be transformed into $$$1$$$; If there are at least two zeros between any two positive numbers, then the median of each interval equals to $$$0$$$, no solution exists.
Consider the sufficiency. If there are two adjacent elements in $$$B$$$ both equals to $$$1$$$ , just select an interval which contains at least three elements and exact one element unequal to $$$1$$$ , and operate once on this interval. After this operation, there are still two adjacent elements in $$$B$$$ both equals to $$$1$$$, so we keep doing this until all elements are transformed into $$$1$$$.
Therefore, if there is a interval $$$[l,r]$$$ which satisfies $$$r-l+1\ge2$$$ and the median of $$$\{B_l,B_{l+1},\dots,B_r\}$$$ equals to $$$1$$$, just perform an operation on $$$[l,r]$$$ , then use the above strategy. It can be shown that such an interval can always be created in several operations with the condition.
• If an interval $$$[i,i+2]$$$ satisfies $$$\{B_i,B_{i+1},B_{i+2}\}=\{0,1,2\}$$$ or $$$\{1,1,2\}$$$ or $$$\{0,1,1\}$$$ or $$$\{1,1,1\}$$$，just perform an operation on $$$[i,i+2]$$$ .
• If $$$[i,i+2]$$$ satisfies $$$\{B_i,B_{i+1},B_{i+2}\}=\{1,2,2\}$$$ , then $$$\{B_i,B_{i+1}\}=\{1,2\}$$$ or $$$\{B_{i+1},B_{i+2}\}=\{1,2\}$$$ . Perform an operation on $$$[i,i+1]$$$ or $$$[i+1,i+2]$$$ .
• If any interval with three elements doesn't satisfy the above conditions, because $$$\exists 1\le i<j\le n,\mathrm{s.t.}j-i\le2,B_i>0,B_j>0$$$ ，there is an interval $$$[i,i+2]$$$ which satisfies $$$\{B_i,B_{i+1},B_{i+2}\}=\{0,2,2\}$$$ or $$$\{2,2,2\}$$$ . Take such an interval $$$[i,i+2]$$$ , perform an operation on $$$[i,i+2]$$$ first, then select an interval which contains at least three elements and exact one element unequal to $$$2$$$ until two adjacent numbers equals to $$$1$$$ and $$$2$$$ respectively. Perform one operation on these two adjacent elements.
Therefore, the sufficiency is proved. So just check whether there is an element in $$$B$$$ equals to $$$1$$$, and whether there is a pair of two positive integers $$$(i,j)$$$ which satisfies $$$1\le j-i\le 2,B_i>0,B_j>0$$$ . The complexity is $$$O(n)$$$.