每日一题 4月22日 K-th Number 二分答案+尺取

居然是二分，真的是没想到。。。

题目大意：
给n个数字ai，从这n个数中取任意长度不小于k的区间，对每个区间都获得其中的第k大的数。将这些区间中获得的第k大的数都放入数组b中，问数组b中的第m大的数字是多少？
n<=100000,0<=ai<=10^9

思路：
枚举区间肯定不行。
这里考虑二分答案。
假设二分当前答案为x，那么我们如果我们可以找到超过m-1个区间，其中这些区间中的第k大数字大于x，就说明当前二分的答案太小了。
二分策略是成立的。
那么如何查找到底有多少个满足条件的区间呢？
这里用尺取法，我们维护两个指针l,r，一开始l=r=1，接着我们往右移动r，同时统计大于x的数字个数t，当数字个数t=k的时候，我们得到了第一个满足条件的区间[l,r]，显然r往后的区间都满足，所以我们可以得到l=1时满足条件的区间个数为n-r+1。
接着我们往右移动l，此时l=2，然后我们根据t=k，看r是否需要往右移动，如果需要移动则移动到t=k为止。那么又可以得到满足条件的区间个数n-r'+1
此时我们的方法出来了，枚举l，然后移动r计算满足条件的区间。
由于r只往右移动，因此复杂度为O(n)。
假设二分，总复杂度为O(nlogn)

代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,a[100040];
long long m;
bool check(int  x){
    int t=0;
    long long cnt=0;
    for(int l=1,r=1;l<=n;l++){

        while(t<k&&r<=n){
            if(r<=n&&a[r++]>x)t++;
        }
      //  cout<<l<<'*'<<r<<endl;
        if(t<k)return false;
        cnt+=(n-r+2);
        if(cnt>m-1)return true;
        if(a[l]>x)t--;
    }
    return false;
}
int main()
{
    int T;
    cin>>T;
    while(T--){
        cin>>n>>k>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        int  l,r;
        l=1;
        r=1000000001;
        while(l<r){
            int mid=l+r>>1;
            if(check(mid))l=mid+1;
            else r=mid;
            //cout<<l<<' '<<r<<endl;
        }
        cout<<r<<endl;
    }
    return 0;
}