这题是真的有点难度，主要在于他的时间复杂度卡的真的特别紧，属于是二分法，前缀和，尺取法，单位元素讨论齐上阵才能够AC，有一点出错了就会TLE，我们来慢慢看思路

二分：实际上这个二分关系真的非常邪门，对于第K大的元素x，那说明他前面起码有k个元素是不小于x的，这就是二分关系（很神奇吧），具体成代码就是

            if(bsum >= m)
            {
                ansout = mid;
                
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }

结合代码来看就很明显了，我们不断二分，那么最后那个ans就是正好“大于等于”的元素，就是我们需要求的

单位元素考虑：众所周知，对于这种“全区间”类型的问题，我们一般考虑使用单个元素来看他所对应的区间，用这种方式来减少原本是On2甚至是更高的复杂度。这里假设我们要看所有大于k的区间的第k大元素有多少个大于mid，那对于每个元素：我们只需要枚举右端点，之后每个右端点枚举左端点看有多少个元素大于等于mid就可以了

前缀和：区间问题用前缀和简化是老生常谈的问题，这里当然也不例外——使用pren前缀和数组来记录大于等于mid的数量，就可以很方便的O1拿到对应区间内大于mid的元素数量

不过有一点很神奇就是我们的前缀和一般是使用类似于1—based的方法：也就是pern[n]是从开始到第n - 1个元素，结合代码就是

for(int r = 1;r <= n;r++)
{
    pren[r] = pren[r - 1] + (num[r - 1] >= mid);//前缀和都忘了，这里应该是num[r - 1]而不是num[r]
}

这样主要是为了能拿到第一个元素，否则lp就要成为-1了，这肯定不对

尺取法：但是为了进一步减少时间：我们知道：如果一个区间可行，那么包含他的子区间肯定就更可行了，也就是说：对于每个右端点——其保底就有上一个元素的贡献，只可能更大不可能更小

文字描述比较抽象，我们来结合代码来看看：

for(int rp = k;rp <= n;rp++)
{
    int lp = 0;
                
    while(pren[rp] - pren[lp] >= k && lp < rp)
    {
        lp++;
                    
        bsum++;
    }
}

也就是贡献lp（左指针）可以反复利用，类似于滑动窗口一样，避免了多次遍历左指针造成的时间浪费

反正还是希望大家保持一定的刷题水平，不要放弃也不要强行越级，我的acm之路应该还没开始就快要结束了，希望大家可以走得更远

AC代码：

/*题目描述
爱丽丝得到了一个包含 N 个数字的数组 A1..N。
现在爱丽丝想按照以下规则用参数 K 构建一个数组 B：
初始时，数组 B 为空。考虑数组 A 中的每个区间。如果这个区间的长度小于 K，就忽略这个区间。否则，在这个区间中找到第 K 大的数字，并将这个数字添加到数组 B 中。
实际上爱丽丝并不关心数组 B 中的每个元素。她只想知道数组 B 中第 M 大的元素。请你帮她找到这个数字。
输入描述
第一行是测试用例的数量。
对于每个测试用例：
第一行包含三个正整数 N (1 ≤ N ≤ 10⁵)；K (1 ≤ K ≤ N)；M。
第二行包含 N 个数字 Aᵢ (1 ≤ Aᵢ ≤ 10⁹)。
保证 M 不大于数组 B 的长度。
输出描述
对于每个测试用例，输出一行，包含数组 B 中第 M 大的元素。*/

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int T; 
    
    cin >> T;
    
    for(int t = 0;t < T;t++)
    {        
        int n,k,m;
        
        cin>>n>>k>>m;
        
        vector<int> num(n,0);
        
        for(int r = 0;r < n;r++)
        {
            cin>>num[r];
        }
        
        int left = 0,right = *max_element(num.begin(),num.end());
        
        int ansout;
        
        while(left <= right)
        {
            int mid = (left + right)/2;
            
            vector<int> pren(n + 3,0);
            
            for(int r = 0;r <= n;r++)
            {
                pren[r] = pren[r - 1] + (num[r] >= mid);
            }
            
            int bsum = 0;
            
            int lp = 0;
            
            for(int rp = k - 1;rp < n;rp++)
            {
                while(pren[rp] - pren[lp] >= k && lp < rp)
                {
                    lp++;
                }
                
                bsum += lp;
            }
            
            if(bsum >= m)
            {
                ansout = mid;
                
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        
        cout<<ansout<<endl;
    }
    
    return 0;
}