题目大意

从给定的A数组，选择全部的长度大于等于K连续子集，构成新的集合，并且从这个集合里面每个拿出第K大加入到B数组中，最后要求B数组中给定的第M大元素。

解题思路

其实这个题目看了挺久都没什么思路和想法，想过去模拟，或者全部保存。。不过空间复杂度和时间复杂度都是 ，有点难顶。走投无路的时候看了一眼题解。二分+尺取。讲道理有点秀到我。参考链接
我们假设初始集合为 ,取K=3，集合为 得到B数组为 再根据题目给定的M输出就行了。
二分：
那么在这里，我们可以发现，每一个输出的元素，都是原先数组里面存在的一个值，那么对于一个在原先数组中的一个值，如果对这个值求第K大数大于等于这个数x的区间个数，如果区间个数大于等于M，说明我们希望x能不能大一点，减少可行区间数目。否则说明我们x取大了，这样去调整二分区间。
因为对与一个x，如果在B中的x前有ans个数，ans大于等于M，很显然得到这个x不可行，需要调整x的取值，反之亦然。
尺取：
上面我们解决了x取值问题，那还有一个问题，就是第K个数大于等于x的区间个数如何快速求解出来？
我们假设从1开始，一直到 个位置存在K个数大于等于x，那么 这个区间内的 ，都存在K个数大于等于x，累加进区间计数器。
如果 之后的数小于x没有影响，如果 之后的数大于等于x，那么对第K大数，一定只会增大。
接下来就是 不动把起始位置1向右移动，这里需要注意，如果 需要把我们记存在多少个大于x数减掉1。否则没有影响直接左区间加一。

时间复杂度O( )

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43536961&returnHomeType=1&uid=919749006

注意一下最多子区间有 开到

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline ll read() {
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e5 + 7;
int a[N];
vector<int> v;
ll n, k, m; //m最大1e10小心给坑开到long long来

bool check(int x) {
    ll ans = 0;  //第k大值大于等于x的子区间个数
    int l = 1, r = 0;
    int num = 0; //区间中大于等于x的数有几个
    while (l <= n) {
        while (num < k && r < n) {
            if (a[r + 1] >= x)   ++num;
            ++r;
        }
        if (num >= k)    ans += (n - r + 1);
        if (a[l] >= x)   --num;
        ++l;
    }
    return ans >= m;
}

int main() {
    int T = read();
    while (T--) {
        n = read(), k = read(), m = read();
        for (int i = 1; i <= n; ++i) {
            a[i] = read();
            v.push_back(a[i]);
        }
        sort(v.begin(), v.end());
        int l = 0, r = v.size() - 1, ans = -1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(v[mid]))  ans = mid, l = mid + 1;
            else    r = mid - 1;
        }
        printf("%d\n", v[ans]);
        v.clear();
    }
    return 0;
}