K-th Number

看直播时似乎很简单，但实际做题时，细节很烦人。
题意：我们要取最终添加完成的数组中第M打的元素
利用二分的思想，这个答案肯定在1 到 1e9之间，那么我们在这个范围内进行二分最终获得答案
那么具体怎么操作呢？
假如我们二分枚举了一个数，我们需要知道在最终排好序的数组中比它大的一共有几个数。
如果比他大或等于他的数大于等于M那么我们可能取小了，也可能最终答案就是他。
如果比他大或等于他的数小于M那么我们一定是取大了。
那么对于我们可能取小也可能取到正确答案的数，也就是第一种情况我们令l = mid+1，进行放大。
对于我们一定取大的数，令r = mid-1，进行缩小。
利用check()函数检查大于等于他的数是否大于等于m
这样最终我们一定会得到正确答案！
正确答案是l-1，也就是最后一次check()为true的mid
假设，我们这一次取到了正确答案，那么按照规则会会进行放大，接下来的每一个数check()都会为false
那么最终l不会变化，答案就是l-1。
那么check(int num)1函数该如何验证大于等于num的数是否大于等于M呢？
对于一个区间[a1,a2,a3,a4,a5,a6,a7,a8]如果，其中大于等于num的数大于等于k那么
这个区间的第k大元素一定也是大于等于k的.这是充要条件！！！！
而如果这个区间中大于等于num的数都大于等于k了，那么我们扩大这个区间的右边界，所得到的区间
也一定满足条件！
那么，我们尺取法，从头到尾进行线性扫描，得出答案。
复杂度O(nlogn)
细节要注意！

#include<iostream>;
#include<algorithm>;
using namespace std;
typedef long long ll;
const int max_n = 1e5 + 100;
ll n, k, m;
ll a[max_n];

bool check(ll x) {
    ll cnt = 0;ll ans = 0;
    for (int i = 1, j = 1;j <= n;j++) {
        if (a[j] >= x)cnt++;
        while (cnt >= k) {
            ans += n + 1 - j;
            if (a[i] >= x)cnt--;
            i++;
        }
    }return ans >= m;
}

ll solve() {
    ll r = 0;ll l = a[1];
    for (int i = 1;i <= n;i++)
        r = max(r, a[i]), l = min(l, a[i]);
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (check(mid))l = mid + 1;
        else r = mid - 1;
    }return l - 1;
}

int main() {
    ios::sync_with_stdio(0);
    int t;cin >> t;
    while (t--) {
        cin >> n >> k >> m;
        for (int i = 1;i <= n;i++)cin >> a[i];
        cout << solve() << endl;
    }
}