K-th Number(二分、滑动窗口)

题目：

一个长为n的序列a[]，所有长度≥k的区间取出第k大的数形成一个新序列b[]。问b[m]的值。

做法：

显然我们不可能求出b中所有数然后取出第m个。
所以想到二分这个数，设为x。然后问题就转化成判定性问题：a[]中所有连续区间的第k大的数≥x的区间个数是否≥m。用滑动窗口的做法使这个judge复杂度为O(n)，可以解决问题。
具体做法就是枚举每个位置作为区间的左端点l，找到对应的右端点r，使[l,r]区间中恰有k个≥x的数。这样我们就能一次统计出左端点为l的且第k大数≥x的区间个数：n-r+1。(r往后每一个位置都满足)。然后左端点l+1时右端点只需在当前的基础上向右扩展就行了。整个过程类似一个窗口在滑动，所以被称为滑动窗口算法，（也被称为双指针或尺取法）。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, k, a[N];
ll m;
bool judge(int x){
    int r = 0, cnt = 0;
    ll ans = 0;
    for (int l = 1; l <= n; ++l){
        while (cnt < k && r < n){
            if (a[++r] >= x) cnt++;
        }
        if (cnt == k) ans += n-r+1;
        if (a[l] >= x) cnt--;
    }
    return ans >= m;
}
int main(void){
    IOS;
    int T; cin >> T;
    while (T--){
        cin >> n >> k >> m;
        int mx = 0;
        for (int i = 1; i <= n; ++i) cin >> a[i], mx = max(mx, a[i]);
        int l = 1, r = mx, ans;
        while (l <= r){
            int mid = (l+r) >> 1;
            if (judge(mid)){
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}