307384: CF1349B. Orac and Medians

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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$。

题目描述

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.

输入输出格式

输入格式


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 $ .

输出格式


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.

输入输出样例

输入样例 #1

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

输出样例 #1

no
yes
yes
no
yes

说明

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] $ .

Input

题意翻译

询问$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$。

加入题单

上一题 下一题 算法标签: