这题要我老命。。二分加尺取（见专栏），秀到了大佬，吓到了我。（现学）

题目

题目描述：
给Alice一个带有N个数字的数组A [1...N]。
现在，Alice想通过参数K按照以下规则构建数组B：
最初，数组B为空。考虑数组A中的每个间隔。如果此间隔的长度小于K，则忽略此间隔。否则，在此间隔中找到第K个最大数字，并将此数字添加到数组B中。
。实际上，Alice不在乎数组B中的每个元素。她只想知道数组B中的第M个最大元素。请帮助她找到这个号码。

输入描述：
第一行是测试用例的数量。对于每一个测试的情况下，第一行包含三个正数N（1≤N≤105）; K（1≤K≤N）; M。
第二行包含N个数甲Ai（1≤Ai≤10 9）。
保证M不大于数组B的长度。

输出描述：
对于每个测试用例，输出一行包含数组B中第M个最大元素的一行。

解析

我们先来梳理一下题目（看题都花了我好好好久，英文看不懂，开了翻译还看了好久）：
  • 对数列A的每个区间求第K大的数插入到B中，再求B中第M大的数。（这就是语言的魅力啊）
然后就是该怎么求的问题了，一个一个算区间当然会超时，所以我们用二分加尺取。

原理：
  1. 我们先看题：我们最终的目标是求出B中第M大的节点——>B的区间长度一定大于等于M && 有M个大于等于答案（第M大位置上的值）的数。
  2. 然后B是怎么来的呢？B是从A里面来的，并且B是取A中的所有第K大的数——>有多少有第K大数的集合，B就有多少项（在没有对集合进行过筛选的情况下）。
  3. 然后！根据第一点中我们得到的结论：有M个大于等于答案（第M大位置上的值）的数——>我们在筛选时，用二分来猜测答案（用x来代表我们猜测的答案（第M大值），也可以说是x相当于第M大值）。
    在本题中我们要求B中至少有K个数大于等于x。（由此尺取出的每个集合都一定满足：len>K）
  4. 按此原理，我们可以用尺取法计算出区间数量。（详情看专栏）
  5. 最后补充：我一开始一直在纠结为什么可以缩减答案（第M大位置上的值）所在集合B的长度，其实是因为缩减了长度以后，删除的只是比答案（第M大数）小的，不影响我们最后求的第M大的这个数。

操作步骤：
  1. 首先，毫无疑问，将该保存的都保存了。
  2. 用二分对答案进行推导，左右分别就取两极：1和INF。
  3. 然后我们就要选取二分条件了：如果区间数量算出来比M（我们要求的最小lenB，见原理1）大或相等，意思就是区间多了，答案更大一点才能缩减区间（取右子集）。反之亦然。
    （缩减区间原因看原理5）
  4. 然后算符合条件的子集数量就用尺取法了。（详情看专栏）

尺取法

首先我们来简单了解一下尺取法：
  • 我们可以使用left和right的左右两个标记划分出一段区域（就像是一把尺子量出这一段），然后在保证区域内的一定条件下向后移动。
  • 所以我们说：尺取法是一种高效的枚举区间的方法。

那我们就讲一下这道题的方法：
  1. 我们先将left和right两个标记放在起点1处，将right后移。（我们在这里取定的条件是：区域至少有K个比x大或相等的值）
  2. 于是我们用num存比x大或相等的值的数量。同时我们用cnt存下满足条件的区域数量。
  3. 接下来，我们只要碰到了比x大或相等的值就让num++。直到num==K的时候我们就应该对区域进行操作了：
    <1>该区域里面已经有K个比x大或相等的数了，所以该区域为一种情况，而right后面每多有一个数，子集就会增加一种情况，所以cnt+=n-i+1。
    <2>我们现在知道有K个比x大或相等的数，然后我们就将范围裁剪到同样情况下的最短（left++），直到左顶点代表的值大于等于x。
    <3>与此同时，由于左端每减少一个左顶点，又会增加子集种数，所以每减少一个，cnt+=n-i+1。
    <4>最后我们就往下一种可能的情况遍历，删除最左端的节点（这个时候最左端节点一定大于等于x：left++，num++），直到right超过终点。
  4. 详情看代码。

AC代码 

#include <iostream>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAX = 1e5 + 7;
//代码预处理
ll N, K, M;//数字总数，第K大数（过程），第M大数（结果）
ll A[MAX];//数据保存数组

template<class T>inline void read(T& res);//整型快读函数
int judge(ll x);//判断区间数（第K大的数大于等于x的）与M的大小

int main() {
    ll T; read(T);
    while (T--) {
        read(N); read(K); read(M);
        for (ll i = 1; i <= N; i++)
            read(A[i]);
        ll left = 1, right = INF;
        while (left < right) {
            ll mid = left + right >> 1;
            if (judge(mid)) left = mid + 1;
            else right = mid;
        }
        printf("%lld\n", left - 1);
    }
    return 0;
}

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;
}
int judge(ll x) {
    //x为二分估计的答案值
    ll cnt = 0;//第K大的数大于等于x的区间个数
    ll num = 0;//当前尺取的区间中大于等于x的数的个数
    for (ll left = 1, right = 1; right <= N; right++) {
        if (A[right] >= x) num++;
        //遇到大于等于x的数便计数
        if (num == K) {
            cnt += N - right + 1;
            //加上该区域向右拓展的区域数量
            while (A[left] < x) {
                cnt += N - right + 1;
                //加上该区域向左拓展的区域数量
                left++;
            }
            //循环删除区域内左边比x小的节点
            left++;
            num--;
            //为了往后遍历，区间第一个节点删除
            //第一个节点一定大于等于x，所以num--
        }
    }
    if (cnt >= M) return 1;
    else return 0;
    //M第M大的数，cnt为理应比M大的区域数量
    //所以当cnt比M大时说明区域多了要缩小，所以返回1取更大的值
}