K-th Number (二分答案)

K-th Number **

感觉题意不太好懂QAQ，这里的第k大是从大到小排序后第k个位置的数。
题意： 从A数组中挑出每个区间内第k大的数放到B数组中，然后输出B中第m大的数；
思路： 首先我们看看暴力怎么做，枚举A中的数 x ，然后怎么去判断这个x是不是A中某一个区间内第k大的数，如果是我们就把x加入到B中，至于如何判断：可以记录每个x出现的位置，然后双指针从x往两边判断是否有k个数>=x 即可；这样最坏是O(n^2)的复杂度，所以不行；
然后此时我们从要输出的B中第m大的数 (要输出的答案) 下手，继续挖掘潜在的性质，如果x是B中的第m大，那x有什么性质呢，性质就是当B从大到小排序后，x的前边有m-1个大于或等于x的数，而这些数都是A中某些区间内第k大的数。有了判断答案的性质，那么我们就可以二分答案了（O(nlogn)）
被二分的元素是A中排序去重后的数，check去寻找在A中 第k大 >= x 的区间有多少个，当check >= m 时说明x取小了；至于如何找第k大>=x的区间个数：当区间内大于等于x的个数 >=k 时 ，第k大自然就 >=x 了，所以还是可以双指针计数；

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long LL;
const int N = 1e5+7;

int a[N],b[N];
LL n,m,k;

LL check(int x)
{
	int j=1,i=1;	//双指针计数
	LL ans=0,num=0;
	 while(j<=n){
        if(a[j]>=x) num++;
        while(num==k){
            ans += n-j+1;		//这里n也设LL 貌似只有ans是LL没用
            if(a[i]>=x) num--;
            i++;
        }
        j++;
    }
	return ans;
}

int main()
{
	IO;
	int T;
	cin>>T;
	while(T--){
		cin>>n>>k>>m;
		for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
		sort(b+1,b+1+n);
		int r = unique(b+1,b+1+n) - b - 1;    //貌似r取a[i]的最大值也行，，，但这样最保险
		int l = 1,ans = 0;
		while(l<=r){
			int mid = l+r>>1;
			if(check(b[mid]) >= m) l = mid + 1,ans = mid;	//注意ans在这里取
			else  r = mid - 1;
		}
		cout<<b[ans]<<endl;
	}
	return 0;
}