https://codeforces.com/contest/1993/problem/D
题目大意
给出一个 $n \ (le 5 \cdot 10^5)$ 长的数组 $a$ 其中 $a_i \le 10^9$。给定一个 $k \ (\le 5 \cdot 10^5)$。
不断地从数组中删去一些长为 $k$ 的子数组（删除后把数组接起来），使得最后的数组长度 $\le k$。 问此时剩余元素的中位数最大可能是多少。剩余元素个数为偶数时中位数取中间偏小的值。
简要题解
由于这个题目总是删除到最少，因此剩下的元素数量是一定的，即 $n % k$ 个，特别的当 $k | n$ 时，为 $k$ 个。 所以实际上，我们知道最终的序列中有多少个数是比中位数大的。
由此，注意到中位数的值是可以二分的。如果中位数 $\ge x$ 是有解的，那么显然取任意的 $y \le x$ 则中位数 $\ge y$ 是有解的。
如何判断能否剩下足够多个 $\ge x$ 的数呢？
首先观察到，因为我们只关注剩下来的数，因此实际上删除这个操作没必要相交。例如 $k = 3$,
$a$ 为 $1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7$
如果删掉下标 $2~4$ 变成 $1 \ 5 \ 6 \ 7$
再删掉下标 $1~3$ 变成 $7$
这与先删 $4~6$ 再删 $1~3$ 的效果是一样的。
考虑 $b_i = [a_i \ge x]$，于是问题变成了，删掉尽可能多的不相交区间保留保留尽可能多的 $1$。
当最后不是剩 $k$ 个时，考虑 $dp[i]$ 为已经考虑到 $i$ 位置删去尽可能多的区间之后剩下 $1$ 的最大数量。这样对于所有的 $k | i$
$$ \begin{equation} dp[i]=\left\{ \begin{aligned} 0, \quad & i = 0 \ or \ k | i \\ dp[i - 1] + b[i], \quad & k < i \\ max(dp[i - 1] + b[i], dp[i - k]), \quad & else \end{aligned} \right. \end{equation} $$特别的当最后需要剩下 $k$ 个时，这种情况需要单独处理。当 $k | i$ 时，还需要让 $dp[i] = 0$，否则我们会得到选超过 $k$ 个剩下的情况。因为对应这些 $i$, $dp[i - 1]$ 的值总是正确的，因此，这时只需用 $dp[i - 1] + b[i]$ 更新一个 $ans$ 即可。
复杂度
$T$：$O(n \log max(a_i))$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n, k; cin >> n >> k;
vector<int> a(n);
for (int& i : a) cin >> i;
int left = n % k;
int need = left ? (left / 2) + 1 : (k / 2) + 1;
// cerr << "need " << need << endl;
vector<int> dp(n + 1);
auto check = [&](int mid) -> bool {
fill(dp.begin(), dp.end(), 0);
int mx = 0;
for (int i = 1; i <= n; i++) {
if (i % k == 0) {
cmax(mx, dp[i - 1] + (a[i - 1] >= mid));
dp[i] = 0;
continue;
}
dp[i] = dp[i - 1] + (a[i - 1] >= mid);
if (i >= k) {
cmax(dp[i], dp[i - k]);
}
}
if (left) return dp[n] >= need;
else return mx >= need;
};
int l = 1, r = *max_element(a.begin(), a.end());
int mid, ans = l;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: C. Light Switches - Codeforces Round 963 (Div. 2)