【每日一题】K-th Number（二分 / 区间问题）

Solution
题意：B的元素取 对于A的每个长度大于k的子区间取第k大元素，求B的第m大元素。

知识点：二分

首先由于数据过大，枚举区间肯定不行，在题解中有一句话非常好：考虑把求值变成验证。
求第m大元素，即判断第k大元素比m大的区间数是否>=m。
想到二分，但是不会计算区间数就很尴尬，还是很佩服大佬们，自己看了题解才想清楚。
用双指针求区间数，当一个区间满足mid为第k大时，左边界为l，右边界为[r,n]，
所以这个区间对答案的贡献为 n-r+1
最后判断的时候如果ans>=m即说明mid小了所以指针右移，反之指针左移。

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("YES") ;}void put2(){ puts("NO") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
const int mo=998244353; const int mod=1000000007;

const int manx=2e6+5;

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

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

int main(){
    ll p=read();
    while(p--){
        n=read(),k=read(),m=read();;
        for(int i=1;i<=n;i++) a[i]=read();
        ll l=1,r=1e9;
        while(l+1<r){
            ll mid= l+r >>1;
            if(pd(mid)) l=mid;
            else r=mid;
        }
        printf("%lld\n",l);
    }
    return 0;
}