【每日一题】K-th Number

中文题意这个大佬博客有翻译 戳我。

思路：

如果遍历每一个大于等于k的区间找第k大的数，复杂度不敢想， （n^2）级别。所以这时候就要用到尺取法了，专栏的办法太秀了。其实我们不在乎第m大的数以外是什么，只要知道第m大的数是什么，所以我们可以二分答案把求值变成验证，再用尺取法找到符合要求的区间数。
原理：
1.居然是找B中第m大的数，那么B中有至少有m个数且至少有m个数大于等于第m大的数。
2.（m个数大于等于第m大的数），这m个数都是A中区间第k大数，也就是第K大数大于B中第m大的数的区间至少有m个。
3.第k大的数大于B中第m大的数的区间，说明区间至少有k个数大于等于k，找到一个符合要求的区间，加入一个数不管大小依然还会满足第k大数大于B中第m大的数，所以可以用尺取法去求第k大的数大于B中第m大的数的区间数（因为要验证二分答案x，需要验证第k大的数大于x的区间数大于等于m）。
4.前面提到我们只在意第m个数是什么而不关心其它数是什么，所以我们只要求得B数组中有多少个数大于等于二分答案x，当数量大于等于m表示x取小了，二分的left右移（当数量等于m时不一定是答案，因为B中可能没有x，也就是x还是小了，只有当x增大到恰好数量小于m，上一个x就是答案），当数量小于m表示m取大了，right左移。

尺取法：
尺取法具体操作就像一个蚯蚓爬行，一头一尾最先在一处，随后头到了某个位置后停下，尾部向前移动到某个位置后停下，一直循环这些动作。这一题主要是用尺取法找到全部只有k个数大于等于x的区间[l,r]，然后可知[l,r~n]也是可行的。
具体操作就是左边界l不动，右边界r右移直到有k个数大于x，记录方案数ans+=n-r+1，接着移动左边界，每移一步都要记录方案数ans+=n-r+1，直到a[l]>=x，左边界l继续移动一步，重复上述过程直到r>n停止。

二分答案： 可以对比前面的二分答案的练习
这里的答案是存在left-1里面的，因为只有当此时的left=mid-1不符合要求时我们才知道之前的mid是最优解。

Code：

#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void read(T &res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
long long m;
int n,k,a[100005];
bool check(int x) {
    long long ans=0;
    int j=1,num=0;
    for(int i=1;i<=n;++i) {
        if(a[i]>=x) ++num;
        if(num==k) {
            ans+=n-i+1;
            while(a[j]<x) {
                ++j; ans+=n-i+1;
            }
            ++j;    --num;
        }//找到第k大的数大于等于x的区间 
    }
    if(ans>=m)    return true;
    return false;
}
int T;
int main() {
    read(T);
    while(T--) {
        read(n),read(k),read(m);
        for(int i=1;i<=n;++i)    read(a[i]);
        int left=1,right=0x3f3f3f3f,mid;
        while(left<=right) {
            mid=left+right>>1;
            if(check(mid)) left=mid+1;
            else right=mid-1;
        }
        printf("%d\n",left-1);
    }
}