Link: The Median of the Median of the Median
考虑二分答案，对中位数进行二分，每次去判断是否比中位数大即可。
我们钦定了一个中位数 \(x\)，对于 \(\{a\}\) 数组，若 \(a_i \ge x\)，则令 \(a_i = 1\)，否则 \(a_i = 0\)，这样有一个好处，我们只关心 \(1\) 和 \(0\) 的数量，就可以知道中位数是否比 \(x\) 大。
如果 \(\{a\}\) 中 \(1\) 的个数多于 \(0\) 的个数，说明中位数大于等于 \(x\)，否则中位数小于 \(x\)。
考虑对所有的 \(\{b_{i,j}\}_{l\le{i}\le{j}\le{r}}\) 求值，不妨枚举左端点 \(l\)，求出一个以 \(l\) 为左端点的 \(\{b_{i,j}\}_{l\le{i}\le{j}\le{r}}\) 的中位数，我们通过前缀和可以求出有多少个数是大于 \(x\) 的。
设 \(cnt[i][j]\) 表示以 \(i\) 为左端点，所有 \(i \le k \le j\) 的 \(b_{i, k}\) 大于等于 \(x\) 的个数，\(pre[0/1]\) 表示 \(a[i \sim j]\) 中 \(0/1\) 的数量，容易发现：
\[cnt[i][j] = cnt[i][j - 1] + [pre[1] > pre[0]] \]考虑如何计算 \(\{c_{l, r}\}_{1\le{l}\le{r}\le{n}}\)，我们枚举 \(r\)，对所有 \(1 \le l \le r\) 求和，因为我们计算的 \(cnt[i][j]\) 是以左端点固定的，因此计算一对 \((l, r)\) 时，对 \(l\) 求 \(cnt[i][r]\) 的后缀和即可，不过因为 \(cnt[i][j]\) 表示的是一个段，因此，\(0\) 的个数变化 \(j - i + 1 - cnt[i][j]\)，\(1\) 的个数变化 \(cnt[i][j]\)，对答案贡献 \(1\) 当且仅当每个段 \(1\) 的个数大于 \(0\) 的个数。
当 \(1\) 的个数大于 \(0\) 时，说明中位数大于等于 \(x\)，二分答案即可。
时间复杂度 \(O(n^2\log{|a|})\)。
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
auto check = [&](int x) -> int {
vector<int> b(n + 1);
vector<vector<int>> cnt(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i ++ ) b[i] = (a[i] >= x);
for (int i = 1; i <= n; i ++ ) {
vector<int> pre(2);
for (int j = i; j <= n; j ++ ) {
pre[b[j]] ++ ;
cnt[i][j] = cnt[i][j - 1] + (pre[1] > pre[0]);
}
}
vector<int> sum(2);
for (int i = 1; i <= n; i ++ ) {
vector<int> pre(2);
for (int j = i; j; j -- ) {
pre[1] += cnt[j][i];
pre[0] += i - j + 1 - cnt[j][i];
sum[pre[1] > pre[0]] ++ ;
}
}
return sum[1] > sum[0];
};
int l = 1, r = 1e9;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
cout << r << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}