$!注意!本方法并非正解,只是在本题的数据强度下可以通过$

其实卡不掉

提供一种思路:分块硬做

一:题意

$m$ 次查找第 $k$ 个大于 $x$ 的数.

二:正确性:

本质暴力查找,肯定正确 $:)$

三:做法:

我们将题目给出的 $n$ 个数每 $\sqrt n$ 个数分为一组,在组内从大到小排序

对于每次查找,使用二分在每组内找到大于 $x$ 的数并累加数量.当累加数量大于 $k$ 时,在本组内按原始顺序一个个判断是否大于 $x$ ,并找到答案.

若累加完所有组后仍小于 $k$ ,则本次查找无解

详见代码

四:时间复杂度

初始化每个块的块内顺序为 $nlog(n)$

每次查找最坏为 $\sqrt n log(n)+\sqrt n$

总时间复杂度为 $m\sqrt n log(n)+m\sqrt n +nlog(n)$

五:代码

#include<bits/stdc++.h>
using namespace std;
struct Node{
	int w[1145],a[1145];
	int len;
} d[1145];
int n,m;
int x,k;
int cnt,res,ans,dgl,rs,pp;
int l,r,mid;

bool cmp(int x,int y){//将sort变为从大到小排序 
	return x>y;
}

void check(int i,int op){//二分查找块内大于x的数 
	
	rs=0;
	l=1,r=d[i].len;	
	
	while(l<=r){
		mid=(l+r)>>1;
		if(d[i].w[mid]<=op)
		  r=mid-1;
		else
		  l=mid+1;  
	}	
  mid=(l+r)>>1;
	rs=mid;
}

int Main(){
	
	cin>>n>>m;
	
	res=sqrt(n);
	
	for(int i=1;i<=n;i++){//建块 
		cin>>d[i/res+1].a[++d[i/res+1].len];
		d[i/res+1].w[d[i/res+1].len]=d[i/res+1].a[d[i/res+1].len];
	}
	cnt=n/res+1;

	for(int i=1;i<=cnt;i++)//初始化块内顺序 
		sort(d[i].w+1,d[i].w+1+d[i].len,cmp);
		
	while(m--){//查找 
		dgl=0;
		ans=-1;
		cin>>x>>k;
		
		if(k>n){
			cout<<-1<<'\n';
			continue;
		}
		
		for(int i=1;i<=cnt;i++){
			check(i,x);
			if(dgl+rs>=k){
				pp=0;
				for(int j=1;j<=d[i].len;j++){//暴力检查答案块 
				  if(d[i].a[j]>x)
				    pp++;
					if(dgl+pp==k){
						ans=d[i].a[j];
						break;	
					}
				}
				break;		
			}
			else
			  dgl+=rs;
		}
		
		cout<<ans<<'\n';
	}
	
	return 0;
}
/*
10 5 
13 11 4 9 7 3 2 6 8 1 
7 4
*/