我是这样瞎写了一下,就是看是否有长度大于1的区间能满足中位数是k,能满足就yes,否则就no,我是用树状数组维护出大于等于k的和小于等于k的再判断和是否大于n*(n-1)/2
但是结束10分钟才调出来(别问我之前在干嘛,问就是在想题)
代码:
#include <cstdio>
#define int long long
using namespace std;
inline int read(){
char ch=getchar();int res=0,w=1;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {res=res*10+ch-'0';ch=getchar();}
return res*w;
}
int t,n,k,a[200001],f[200001],tree[200002];
inline int lowbit(int x) {return x&(-x);}
inline void add(int p,int x){
while(p<=2*n+1) {tree[p]+=x;p+=lowbit(p);}
}
inline int ask(int x){
int res=0;
while(x) {res+=tree[x];x-=lowbit(x);}
return res;
}
void solve(){
n=read();k=read();int o=0,ans1=0,ans2=0;
for(int i=1;i<=n;i++) {a[i]=read();o+=a[i]==k;}
if(o==n) {puts("yes");return;}
for(int i=1;i<=2*n;i++) tree[i]=0;
for(int i=1;i<=n;i++)
{
if(a[i]>=k) f[i]=f[i-1]+1;
else f[i]=f[i-1]-1;
ans1+=ask(f[i]-1+n);add(f[i-1]+n,1);
}
for(int i=1;i<=2*n;i++) tree[i]=0;
for(int i=1;i<=n;i++)
{
if(a[i]>k) f[i]=f[i-1]+1;
else f[i]=f[i-1]-1;
ans2+=ask(2*n+1)-ask(f[i]+n);add(f[i-1]+n+1,1);
}
if(ans1+ans2>n*(n-1)/2) puts("yes");
else puts("no");
}
signed main(){
t=read();while(t--) solve();
return 0;
}