题意简述

给定数组 $a$，每次删除一个长度为 $k$ 的连续子数组，直到剩余长度 $\le k$。求剩余数组的最大可能中位数。

关键结论

每次删除长度为 $k$ 的连续段，最终剩余的元素在原序列中的下标必须满足：

• 第一个剩余元素下标 $i_1 \equiv 1 \pmod{k}$；
• 相邻剩余元素下标 $i_{t+1} \equiv i_t + 1 \pmod{k}$；
• 最后一个剩余元素下标 $i_m \equiv n \pmod{k}$。

由此可得，最终剩余长度 $m$ 是唯一确定的：

$$m = \begin{cases} k, & \text{if } n \bmod k = 0 \\ n \bmod k, & \text{otherwise} \end{cases} $$

且剩余元素的下标模 $k$ 依次为 $1, 2, \dots, m$。

因此问题转化为：从原序列中按顺序选出 $m$ 个元素，使得它们的下标模 $k$ 恰好依次为 $1, 2, \dots, m$，且下标严格递增。我们需要最大化这 $m$ 个元素的中位数。

二分答案

二分最终中位数的值 $mid$。定义 $b_i = 1$ 若 $a_i \ge mid$，否则 $b_i = 0$。中位数 $\ge mid$ 等价于选出的 $m$ 个元素中，至少有 $need = \lfloor m/2 \rfloor + 1$ 个 $1$。

判定问题：能否按照上述模条件选出一个长度为 $m$ 的递增下标序列，使得其中 $1$ 的个数 $\ge need$。

DP 实现

将原序列按照下标模 $k$ 分成 $k$ 个类。我们只需要考虑类 $1, 2, \dots, m$。对于每个类 $i$，收集所有满足 $i \bmod k$ 为 $i$ 的元素（即下标 $\equiv i \pmod k$），记录它们的下标和 $b$ 值，并按下标排序。

DP 状态：$f$ 表示处理到当前类时，选出的序列末尾在该类元素的某个位置时，序列中 $1$ 的最大个数。
转移：对于类 $i$，从前一个类 $i-1$ 中选取下标小于当前元素的下标，取最大 $f$ 值，然后加上当前元素的 $b$。可使用双指针优化，因为相邻类元素的下标天然有序。

• 初始：类 $1$ 的 $f = b$。
• 最终答案：类 $m$ 中所有 $f$ 的最大值。

若最大值 $\ge need$，则 $mid$ 可行。

复杂度：单次检查 $O(n)$，二分 $O(\log \max a)$，总时间 $O(n \log \max a)$，可过。

参考代码

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

int n, k;
vector<int> a;

bool check(int mid) {
    int m = n % k;
    if (m == 0) m = k;
    int need = m / 2 + 1;

    vector<vector<pair<int, int>>> classes(m + 1);
    for (int i = 0; i < n; ++i) {
        int r = (i + 1) % k;
        if (r == 0) r = k;
        if (r <= m) {
            classes[r].push_back({i, (a[i] >= mid) ? 1 : 0});
        }
    }

    vector<int> f;
    for (int i = 1; i <= m; ++i) {
        vector<int> new_f(classes[i].size(), -1e9);
        if (i == 1) {
            for (int j = 0; j < (int)classes[i].size(); ++j)
                new_f[j] = classes[i][j].second;
        } else {
            const auto& prev = classes[i - 1];
            const auto& cur = classes[i];
            int ptr = 0, max_f = -1e9;
            for (int j = 0; j < (int)cur.size(); ++j) {
                int idx = cur[j].first;
                while (ptr < (int)prev.size() && prev[ptr].first < idx) {
                    max_f = max(max_f, f[ptr]);
                    ptr++;
                }
                if (max_f > -1e8)
                    new_f[j] = max_f + cur[j].second;
            }
        }
        f = move(new_f);
    }

    int best = -1e9;
    for (int x : f) best = max(best, x);
    return best >= need;
}

void solve() {
    cin >> n >> k;
    a.resize(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int l = 1, r = 1e9;
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << "\n";
}

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