二分检验

描述见题面
思路：二分一个值x，检验一下原来序列，看有多少个子序列含有多于k个比x大的值，每找到一个就记录，寻找的时候按照尺取的办法，用一个变量来存当前l和r之间含有多少个大于x的值，只要这个数等于k，那么右指针往右的所有数都算进区间作为子序列，最后看一下，是否存在多于m个子区间，其中含有多于k个比x大的值。
代码：

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

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

bool check(int x)
{
    LL cnt = 0, num = 0;  // 分别记录存在多少个区间符合条件以及当前l，r之间有多少个比k大的数
    int l = 0;
    for (int r = 0; r < n; r ++ )
    {
        if (a[r] >= x) num ++ ;
        if (num >= k)  // 大于等于二分值的数已经有k个了
        {
            cnt += n - r;
            while (a[l] < x)
            {
                l ++ ;
                cnt += n - r;
            }

            l ++ ;  // 为使双指针能够继续走，这里让l往前走一位
            num -- ;
        }
    }

    return cnt >= m;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        cin >> n >> k >> m;
        int max_ = 0;
        for (int i = 0; i < n; i ++ ) 
        {
            cin >> a[i];
            max_ = max(a[i], max_);
        }

        int l = 0, r = max_;
        while (l < r)  // 二分值k
        {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }

        cout << l << endl;
    }

    return 0;
}