关于今晚CF Div.2的D
  • 板块学术版
  • 楼主Register
  • 当前回复23
  • 已保存回复23
  • 发布时间2020/5/12 23:19
  • 上次更新2023/11/7 02:34:10
查看原帖
关于今晚CF Div.2的D
80679
Register楼主2020/5/12 23:19

我是这样瞎写了一下,就是看是否有长度大于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;
}
2020/5/12 23:19
加载中...