Question

将所有连续区间中第K大的数放入一个新的数组B中，求数组B中第M大的数为多少？

Solution

二分+尺取
答案具有单调性，故考虑二分。看了邓老师的题解之后发现居然可以二分诶
那么问题就是check函数该如何写了，这里要用到尺取法判断。
我们求任意连续区间中第K大的数的数量，若数量则L=mid+1,反之R=mid。
当一个连续区间中有K个数的时候，他的右边界剩余数的数量与其组成的连续区间均满足，故ans+=n-r+1记录。
然后左指针更新。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 1e5 + 5;

ll n,k,m,a[N];

bool check(ll x){
    ll l=1,r=0,num=0;
    ll ans=0;
    while(l<=n){
        while(r<n && num<k)
            if(a[++r]>=x) num++;
        if(num==k) ans+=n-r+1;
        if(a[l]>=x) num--;
        ++l;
    }
    return ans>=m;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        cin>>n>>k>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        ll L=1,R=1e9+1,mid,ans=0;
        while(L<R){
            mid=(L+R)/2;
            if(check(mid)) L=mid+1,ans=mid;
            else R=mid;
        }
        cout<<ans<<'\n';
    }
    return 0;
}