【Codeforces Round #641 (Div. 2) 】D - Orac and Medians

我們用“感染”來描述一個中位數指派給一個區間的過程。

①易發現如果元素k的左右任意有一個>=k的數時，k就可以感染整個數組。

②如果任意一個區間可以被感染成一個>=k的數時，k元素的左側或右側一定會被感染成>=k的數。利用結論①即可知k可感染整個數組。

#include<bits/stdc++.h>
#define rep(i,b) for(int i=1;i<=b;i++)
#define drep(i,b) for(int i=b;i>=1;i--)
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define pr pair<int,int>
#define ff first
#define ss second
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
const int mod=1e9+7;
int n,m,k,t,x,y,z;
int a[N];

bool solve(int ans=0) {
    cin>>n>>k;
    rep(i,n) cin>>a[i];
    int fg=0;
    rep(i,n) if(a[i]==k) fg=1;
    if(!fg) return false;
    if(n==1) return true;
    fg=0;
    int t=0;
    rep(i,n) {
        if(a[i]>=k) t++;
        else t--;
        if(fg&&t>0) return true;
        if(a[i]>=k) fg=1;
        if(t<0) t=0,fg=0;
    }
    return false;
}

#undef int
int main() {
    ios::sync_with_stdio(false);
    int T;cin>>T;
    while(T--)
        if(solve()) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
}