题目要求：给定一个长度为 ( n ) 的数组 ( a )，对所有区间 ([l, r])（(1 \le l \le r \le n)），求出每个区间第 ( K ) 大的数（若区间长度 < K，则忽略该区间），然后将所有这些“第 K 大”收集起来，再求这整个集合中的第 ( M ) 大的数。

核心思路：二分答案 + 双指针/尺取法计数

我们无法枚举所有区间，但可以二分答案：
设最终答案为 ( X )，若我们能快速判断“至少有多少个区间的第 K 大 ≥ X”，即可判断 ( X ) 是否 ≥ 真实答案。

一个区间的第 K 大 ≥ X
⇔ 该区间中 ≥ X 的数 ≥ K 个
（因为将区间内数降序排列后，第 K 个 ≥ X 当且仅当前 K 个都 ≥ X，等价于总共有至少 K 个 ≥ X 的数）

因此，对一个给定的 ( X )，问题转化为：

有多少个区间 ([l, r]) 满足：区间内 ≥ X 的元素个数 ≥ K？

此问题可用双指针（滑动窗口）在 ( O(n) ) 时间内解决。

算法步骤

Step 1：：定义 check(X)

典型双指针问题：

long long count_GE_K(const vector<int>& a, int K, int X) {
    int n = a.size();
    long long cnt = 0;
    int left = 0;
    int ones = 0;
    for (int right = 0; right < n; ++right) {
        if (a[right] >= X) ones++;
        while (ones >= K) {
            // [left, right] 满足 ones >= K，则 [left, right], [left+1, right], ..., [right, right] 都满足
            cnt += (n - right);   // 固定 left，右端点 ≥ right 的都合法（因为扩展右端点不会减少 ones）
            if (a[left] >= X) ones--;
            left++;
        }
    }
    return cnt;
}

注意：上面逻辑是常见错误点！
正确做法是：对于每个 right，找到最小的 left 使得 [left, right] 中 ≥X 的数 ≥ K，那么所有 l ∈ [0, left_min] 对应的 [l, right] 都满足条件（因为缩短左端点只会增加/不变元素个数）。

正确双指针写法：

long long count_GE_K(const vector<int>& a, int K, int X) {
    int n = a.size();
    long long cnt = 0;
    int left = 0;
    int ones = 0;
    for (int right = 0; right < n; ++right) {
        ones += (a[right] >= X);
        // 缩小窗口直到 ones < K（即 [left, right] 是最后一个满足 ones >= K 的起点）
        while (ones >= K) {
            ones -= (a[left] >= X);
            left++;
        }
        // 此时 [0, left-1] 开头、以 right 结尾的区间都满足 ones >= K
        cnt += left;  // l = 0,1,...,left-1 共 left 个
    }
    return cnt;
}

举例验证：

a = [3,1,4,2], K=2, X=2 → b = [1,0,1,1]
right=0: ones=1 <2 → cnt+=0, left=0
right=1: ones=1 <2 → cnt+=0
right=2: ones=2 ≥2 → enter while: subtract a[0]=1 → ones=1, left=1 → exit
          cnt += left = 1  （即 [1,2]: [1,4] 满足？b=[0,1,1] sum=2 ✓；[0,2]: [3,1,4] 也满足但 left 已移出？）
→  错误！

问题出在：当 right=2 时，[0,2] 和 [1,2] 都满足，但上面只加了 left=1，漏了 [0,2]。

正确逻辑应是：维护窗口 [l, r] 中 ones ≥ K 的最小 l（即 l_min），则所有 l ≤ l_min 的起点都合法。

更稳妥写法：固定 r，求最大 l_max 使得 [l_max, r] 中 ones ≥ K，则合法 l 为 0 ~ l_max，共 l_max + 1 个。

但用双指针找 l_max 不方便（要扩展左端点），所以我们换种方式：

维护一个窗口 [l, r] 使得其中 ones = K-1，则 l 是第一个不满足的位置，l-1 是最后一个满足的位置。

经典模板（计数 ≥K 的区间数）：

long long count_GE_K(const vector<int>& a, int K, int X) {
    if (K == 0) return 1LL * a.size() * (a.size() + 1) / 2;
    int n = a.size();
    long long cnt = 0;
    int l = 0;
    int sum = 0;
    for (int r = 0; r < n; ++r) {
        sum += (a[r] >= X);
        // 缩小 l 使得 [l, r] 中 sum == K-1（即刚好不够）
        while (sum >= K) {
            sum -= (a[l] >= X);
            ++l;
        }
        // 此时 [0, l-1] 作为起点，[start, r] 都满足 sum >= K
        cnt += l;  // start = 0,1,...,l-1
    }
    return cnt;
}

再验证：

a = [3,1,4,2], K=2, X=2 → b=[1,0,1,1]
r=0: sum=1 <2 → l=0, cnt+=0
r=1: sum=1 <2 → cnt+=0
r=2: sum=2 ≥2 → enter while: sum-=a[0]>=2?1 → sum=1, l=1 → exit
      cnt += l = 1  （start=0: [0,2] 满足 ✓）
r=3: sum += a[3]>=2?1 → sum=2 ≥2
      while: sum-=a[1]>=2?0 → sum=2, l=2; still ≥2
             sum-=a[2]>=2?1 → sum=1, l=3 → exit
      cnt += l = 3  （start=0:[0,3], start=1:[1,3], start=2:[2,3] — 共3个）

总 cnt=1+3=4

枚举所有 len≥2 区间（共 3+2+1=6 个）：
[0,1]: [3,1] → 第2大=1 <2 → 不计  
[0,2]: [3,1,4] → 排:4,3,1 → 第2大=3 ≥2 ✓  
[0,3]: [3,1,4,2] → 4,3,2,1 → 第2大=3 ≥2 ✓  
[1,2]: [1,4] → 4,1 → 第2大=1 <2 ✗  
[1,3]: [1,4,2] → 4,2,1 → 第2大=2 ≥2 ✓  
[2,3]: [4,2] → 4,2 → 第2大=2 ≥2 ✓  
→ 共4个 ✓

Step 2：二分答案

  • 设 ( f(X) = ) 有多少个区间的第 K 大 ≥ X
  • ( f(X) ) 是非递增函数：X↑ ⇒ 满足条件的区间数↓
  • 要找最大的 ( X ) 使得 ( f(X) \ge M )
    （因为 ( S ) 中第 ( M ) 大 = 满足 ( \ge X ) 的数 ≥ M 的最大 X）

标准二分：

int low = 1, high = 1e9;
while (low < high) {
    int mid = (low + high + 1) / 2;  // 上取整，避免死循环
    if (count_GE_K(a, K, mid) >= M) {
        low = mid;
    } else {
        high = mid - 1;
    }
}
answer = low;

代码实现

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll count_GE_K(const vector<int>& a, int K, int X) {
    int n = a.size();
    if (K == 0) return 1LL * n * (n + 1) / 2;
    ll cnt = 0;
    int l = 0;
    int sum = 0;
    for (int r = 0; r < n; ++r) {
        sum += (a[r] >= X);
        while (sum >= K) {
            sum -= (a[l] >= X);
            ++l;
        }
        cnt += l;  // start in [0, l-1]
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, K;
    ll M;
    while (cin >> n >> K >> M) {
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }

        int low = 1, high = 1e9;
        while (low < high) {
            int mid = (low + high + 1) >> 1;
            if (count_GE_K(a, K, mid) >= M) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        cout << low << '\n';
    }
    return 0;
}

复杂度分析

  • 时间：二分 ( O(\log \max a_i) \approx 30 ) 次，每次 count_GE_K 为 ( O(n) ) → 总 ( O(n \log 10^9) )
  • 空间：( O(n) )

满足 ( n \le 10^5 ) 要求（HDU 实测 300~500 ms）

总结

  • 第 K 大 ≥ X ⇔ 区间中 ≥ X 的数 ≥ K
  • 二分答案 + 双指针计数是解决“第 M 大的第 K 大”类问题的标准范式
  • 双指针写法务必验证边界（尤其是 K=1, K=n 极端情况）