题意

• 给定一个长为n的数组a，对于他的每个区间拿出他的第K大元素，将所有的第K大元素进行排序，请问其中的第M 大是多少

思路

• 转化1：第K大数比X小的区间个数不能超过M-1个
• 转化2：区间中大于等于X的元素超过K个的区间小于M个
• 转化3：二分M，按上述要求检查所有可能的区间
• 转化4：对于找区间这个事情，如果找到了一个说明这个区间右界往后的每一个区间超过X的数都多余K个——双指针

注意

• 第K大是一个神奇的概念，例如{1,1,1,2,2,2,2,2,3}，第3，4，5 大数都是2，所以当x=2，k=4时，不能只考虑大于的，等于的也得考虑，同理，在后面更新左界的时候，就不能取等

AC代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,k,m,a[202020];

int judge(int x){
    int l=1,r=1;
    int cntm=0;        
    int cntk=0;
    for(;r<=n;r++){
        if(a[r]>=x)cntk++;//这里可以取等，恶心
        if(cntk==k){
            while(a[l]<x){
                cntm+=n-r+1;
                l++;
            }
            cntm+=n-r+1;
            l++;
            cntk--;
        }
    }
    if(cntm>=m)return 1;
    else return 0;
}


signed main(){
    int t;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld",&n,&k,&m);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
        }
        int l=1,r=1e9+10;
        //二分第m大数x
        while(l<=r){
            int x=(l+r)>>1;
            if(judge(x))l=x+1;
            else r=x-1;
        }
        printf("%lld\n",r);
    }
    return 0;
}