K-th Number题解

题意：就是给你N个树，然后你去把这些数分成很多个区间然后把这些区间的找到他的第K大，然后这些第K大的数又组合成一个新的数组，最后找出这个新的数组里面的第M大。
苦苦想了很久都不知道如何做，还是看了题解才豁然开朗。（太菜了）
其实就是二分+尺取法，首先就是二分一个答案，然后每次去找第K大，我们可以开一个cnt记录当前这个答案在原数组的尺取区间是第K大，然后cnt==k 我们就应该找去可以满足的区间数，比如当前一个满足区间是1-i，那么是不是i-n这里面可以一直延续到最后一个数，每次形成一个新的区间，那么是不是就有 n-i+1个这样的区间，自己可以好好想一下，当然这是大范围，列如i=10，那么1-10这个区间就已经有第K大的数了，但是有可能1-4的区间的数组小于了我们的答案，是不是我们就可以2-i，3-i，4-i，这些又是一个新区间，但是答案却不变，依旧是n-i+1，所以每次我们还要在cnt=k的时候while一下左边的端点是不是有小于第k大的数，最后我们所有的区间数和M比较一下，如果小于M，那么说明在新数组里面找不到第M大，反正就有，而且你的二分答案，将会是最优。
PS:最后为啥输出l-1呢？

da:如果当前的mid符合情况，mid的有可能是最终的答案，但是我写的那里让l = mid + 1了，所以最后一次，得到的mid为最终答案的时候，l又等于mid+1了，所以最后mid为答案，l=mid+1，所以输出l-1

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof b);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
ll ans[maxx];
ll n,m,k;
ll judge(ll x)
{
    ll sum=0,cnt=0,j=1;
    for(int i=1;i<=n;i++)
    {
        if(ans[i]>=x) cnt++;
        if(cnt==m)
        {
            sum+=n-i+1;
            while(ans[j]<x)
            {
                j++;
                sum+=n-i+1;
            }
            j++;
            cnt--;
        }
    }
    if(sum>=k)
        return 1;
    else
        return 0;
}
int main()
{
    int a;
    cin>>a;
    while(a--){
    cin>>n>>m>>k;
    ll ma=-1e9;
    for(int i=1;i<=n;i++)
    cin>>ans[i];//ma=max(ma,ans[i]);
    ll l=1,r=2e9;
    while(l<r)
    {
        ll mid = l + r >> 1;
        if(judge(mid)) l=mid+1;
        else r=mid;
    }
    cout<<l-1<<endl;
    }
    return 0;
}