NC14301 K-th Number(二分+尺取）

题意

有T组数据。
每组数据给定长度为 的数组 ，对所有长度大于等于 的连续子段，取出其第 大放入数组 中。求数组 的第 大。

分析

先吐槽一下，第 大表意真的不明啊！！
这题简直是套路套路套路题。前几天刚做过类似的。。。
考虑二分答案然后检查可行性。（没做过的话真难想啊！！
我们不妨设 ，看看满足这个条件的情况是什么。其实就是数组大于等于 的至少有 个。
现在我们就要求 数组大于等于 的数有多少个，即有多少个区间的第 大大于等于 。
然后我们让：

1. 时，
2. 时，

记 为 的前缀和。
当区间 的和大于等于 时，说明这个区间有至少个大于等于 的数，那么这个区间的第 大一定大于等于 。
因此，假设 为右端点，那么对于所有 的 区间 都能满足该条件。
一开始想的是对于每个 ，用树状数组求 有多少个，属实智障。
再想想，当某个 满足时， 一定也都满足，我们找到最大的 就可以了。然后 参与的区间个数就是 了。
然后对于每个 ，其所对应的最大 一定是单调不减的。我们从 到 扫一遍即可。
复杂度是
还有个细节， 要开 ！！！居然因为这个 了好一会儿。。

代码如下

#include <bits/stdc++.h>
#define N 250005
using namespace std;
typedef long long LL;
LL z = 1;
LL read(){
    LL x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int a[N], s[N], n, k;
LL m;
int ok(int x){
    int i, j, l = 0;
    LL sum = 0;
    for(i = 1; i <= n; i++) s[i] = s[i - 1] + (a[i] >= x);
    for(i = k; i <= n; i++){
        while(s[i] - s[l] >= k) l++;
        sum += l;
    }
    return sum >= m;
}
int main(){
    int i, j, T, l, r, mid;
    T = read();
    while(T--){
        n = read(); k = read(); m = read();
        l = r = 1;
        for(i = 1; i <= n; i++) a[i] = read(), r = max(r, a[i]);
        while(l < r){
            mid = l + r + 1 >> 1;
            if(ok(mid)) l = mid;
            else r = mid - 1;
        }
        printf("%d\n", l);
    }
    return 0;
}