题目大意

给定长为 的序列，求其所有长度 的子区间的第 大数，所构成多重集的第 大数。

题解

二分。

现判定 。问题转化为求第 大数 的子区间个数，若其 则判定失败，否则判定成功。

如果将原始序列转化为一个 01 序列，某位置上为 表示原始序列上这个位置的数 ，否则为 ，那么区间个数就等于为该 01 序列中子区间和 的区间个数。这个显然是可以用尺取法计算的。

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, k;
ll m;
int a[100005], b[100005];
void init(){
    n = read(), k = read();
    scanf("%lld", &m);
    for (int i = 1; i <= n; ++i)    
        a[i] = read(), b[i] = a[i];
    sort(b + 1, b + n + 1);
}
bool judge(int x){
    ll res = 0;
    for (int i = 1, cur = 0, cnt = 0; i <= n; ++i){
        while (cur < n && cnt < k){
            ++cur;
            if (a[cur] > x) ++cnt;
        }
        if (cur == n && cnt < k) break;
        res += (n - cur + 1);
        if (a[i] > x) --cnt;
    }
    return res < m;
}
void solve(){
    int l = 1, r = n;
    while (r > l){
        int mid = (l + r) >> 1;
        if (judge(b[mid]))
            r = mid;
        else l = mid + 1;
    }
    printf("%d\n", b[l]);
}
int main(){
    int T = read();
    while (T--){
        init();
        solve();
    }
    return 0;
}

小结

有的时候二分判定的不仅仅是一个答案，还可以是一个答案区间。

这个大部分时候都是显然的，但是有的时候会忽略。