$O(nlogn)$ 二分，前缀和

首先，一定存在一个 $v_{max}$ ，且 $v_{max} \geq v$ 一定成立（ $v$ 表示子中值集合）。

"存在一个子中值 $≥v$ "这句话是单调的。所以我们可以通过二分答案来找到最大的 $v$, 即$v_{max}$ 。

现在考虑如何验证：是否存在一个子中值 $\geq v$ （二分的 $v$ 是否符合答案）。

首先可以创建一个新数组 $s$ , 其中 s[i] = a[i] >= v ? 1 : -1.

在 $s$ 中如果存在一个满足下列要求的区间 $[l, r]$，则说明存在子中值 $\geq v$

• $r - l + 1 \geq k$，区间长度至少为 $k$
• $\sum_{l}^{r} s[i] >= 0$，区间之和至少为 $0$

这个验证可以通过对 $s$ 数组求前缀和，使得问题在 $O(n)$ 解决。

前缀和后，枚举右端点 $r$ , 维护 $[1,r - k]$ 区间的最小值的下标 $idx$，$s[r] - s[idx] >= 0$ 即成立。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

#define x first
#define y second

const int N = 2e5 + 10, mod = 998244353;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> v(n + 1);
    for(int i = 1; i <= n; i ++)
        cin >> v[i];
    
    int ansl, ansr;
    int l = 1, r = n;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        
        vector<int> s(n + 1);
        for(int i = 1; i <= n; i ++)
        {
            if(v[i] >= mid) s[i] = 1;
            else s[i] = -1;
            s[i] += s[i - 1];
        }
        
        bool flag = 0;
        int idx = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(i >= k)
            {
                if(s[i] - s[idx] >= 0)
                {
                    flag = 1;
                    ansl = idx + 1;
                    ansr = i;
                    break;
                }
                if(s[i - k + 1] < s[idx]) idx = i - k + 1;
            }
        }
        
        if(flag) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
	int t = 1;
	cin >> t;
	while(t --)
		solve();
}