C. 进击的序列

    传统题 文件IO:seq 2000ms 256MiB

进击的序列

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题意描述

水王有一个正整数序列a1,a2,ana_1,a_2,…,a_n

冷藏柜可以在一个操作中选择该序列的任意子段 [lr][l…r] ,并将 al,al+1ara_l,a_{l+1},…,a_r 的所有值替换为{al,al+1ar} \{a_l,a_{l+1},…,a_r\} 的中位数。

在这个问题中,对于多重整数集 ssss 的中位数的值等于第 s+12\lfloor \dfrac{ |s|+1}{2} \rfloor 小的数。其中s|s|表示集合ss 里的数字数量,x\lfloor {x }\rfloor表示对xx向下取整。

例如, {1,4,4,6,5}\{1,4,4,6,5\} 的中位数是 44 ,而 {1,7,5,8}\{1,7,5,8\} 的中位数是 55

水王希望冷藏柜通过这些操作使 a1=a2==an=ka_1=a_2=…=a_n=k

冷藏柜认为这是不可能的,他不想做人浪费时间,所以他决定问你是否可以满足水王的要求,他可能会问你多次这些问题。

输入格式

第一行一个整数 tt 表示询问的数量。

对于每个询问,第一行包含两个整数 n(1n100 000)n(1\leq n\leq 100\ 000)k(1k109)k(1≤k≤10^9) ,第二行包含 nn 个正整数 a1,a2an(1ai109)a_1,a_2,…,a_n(1≤a_i≤10^9)

nn 的总和最多是 100 000100\ 000

输出格式

输出应该包含 tt 行。对于第 ii 组数据如果可能使所有整数在某些操作后为 kk ,第 ii 行应该输出 ”yesyes“,否则输出 ”nono

样例输入

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

样例输出

no
yes
yes
no
yes

样例解释

在第一个查询中,冷藏柜不能将所有元素转换为 33

在第二个查询中, a1=6a_1=6 已经得到满足。

在第三个查询中,冷藏柜可以选择完整的数组并将所有元素转换为 22

在第四个查询中,冷藏柜不能将所有元素转换为 33

在第五个查询中,冷藏柜可以先选择 [1,6][1,6] ,再选择 [2,10][2,10]

数据规模

数据点编号 t= n<= k,a[i]<=
1,2,3,4 1,2,3,4 2 2 10 10
5,6,7,8 5,6,7,8 10 10 20 20
9,10,11,12 9,10,11,12 20 20
13,14,15,16 13,14,15,16 50 50 6250 6250 109 10^9
17,18,19 17,18,19 100 100 100000 100000
20 20 10 10

友爸信奥-2024CSPJ组复赛-十连测-第三测

未参加
状态
已结束
规则
IOI(严格)
题目
4
开始于
2024-9-29 12:30
结束于
2025-2-28 8:30
持续时间
3644 小时
主持人
参赛人数
45