题目解析

给定数组 $a$（元素在 $1$ 到 $n$ 之间）和整数 $k$，定义 $v$ 是子中位数如果存在长度 $\ge k$ 的子数组，使得 $v$ 是该子数组的一个中位数（按题目中的中位数定义）。需要找到最大的子中位数 $v_{\max}$ 并输出任意一个对应的子数组。

关键观察

• 对于固定的 $v$，定义 $b_i = 1$ 若 $a_i \ge v$，否则 $b_i = -1$。则子数组 $[l,r]$ 满足 $\ge v$ 的元素数量 $\ge \lceil (r-l+1)/2 \rceil$ 当且仅当 $\sum_{i=l}^r b_i \ge 0$。
• 如果 $v$ 是子数组的中位数，则它同时满足 $\ge v$ 的数量 $\ge \lceil m/2 \rceil$ 和 $\le v$ 的数量 $\ge \lceil m/2 \rceil$。但可以证明，对于最大可能的 $v$，只需要检查第一个条件即可（因为此时第二个条件自动成立）。
• 因此，最大子中位数等于最大的 $v$ 使得存在长度 $\ge k$ 的子数组，其 $\sum b_i \ge 0$。这是一个典型的“存在长度至少为 $k$ 的子数组和非负”问题。

算法步骤

1. 二分答案 $v$，范围 $[1, n]$。
2. 对于每个 $v$，构造数组 $b$：$b_i = 1$ 若 $a_i \ge v$，否则 $b_i = -1$。
3. 计算前缀和 $pref[0]=0$，$pref[i] = \sum_{j=1}^i b_j$。
4. 遍历右端点 $r$ 从 $k$ 到 $n$：
   • 维护前 $r-k$ 个前缀和的最小值 $min\_pref$ 及其对应的位置 $min\_pos$（即最小的 $l-1$）。
   • 若 $pref[r] \ge min\_pref$，则存在满足条件的子数组 $(min\_pos+1, r)$。
   • 同时记录该 $v$ 可行，并保存区间。
5. 二分找到最大的可行 $v$，然后输出对应的 $v$ 和区间。

时间复杂度：$O(n \log n)$ 每个测试用例，总和 $O(N \log N)$，$N \le 3\times 10^5$，可以通过。

代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        int lo = 1, hi = n;
        int ans_v = 1, ans_l = 0, ans_r = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            vector<int> b(n);
            for (int i = 0; i < n; ++i) b[i] = (a[i] >= mid) ? 1 : -1;
            vector<int> pref(n + 1);
            pref[0] = 0;
            for (int i = 0; i < n; ++i) pref[i+1] = pref[i] + b[i];
            int min_pref = pref[0];
            int min_pos = 0;
            bool ok = false;
            int best_l = -1, best_r = -1;
            for (int r = k; r <= n; ++r) {
                // 维护前 r-k 个前缀的最小值
                // 当 r 增加时，新的候选 l-1 = r-k
                int idx = r - k;
                if (pref[idx] < min_pref) {
                    min_pref = pref[idx];
                    min_pos = idx;
                }
                if (pref[r] >= min_pref) {
                    ok = true;
                    best_l = min_pos + 1; // 注意下标从1开始
                    best_r = r;
                    break;
                }
            }
            if (ok) {
                ans_v = mid;
                ans_l = best_l;
                ans_r = best_r;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        cout << ans_v << " " << ans_l << " " << ans_r << "\n";
    }
    return 0;
}