Max Median

Created by LXC on Thu Jan 11 13:47:18 2024

https://codeforces.com/problemset/problem/1486/D

ranting: 2100

tag: binary search, data structures, dp

problem

给定一个长度为 $n$ 的序列 $a$，求所有长度 $\ge k$ 的连续子序列中，中位数的最大值。定义中位数是一个长度为 $x$ 的序列升序排序后的第 $\left\lfloor\frac{x+1}{2}\right\rfloor$ 位的值。

$1\le n, k\le 2\times 10^5$，$1\le a_i\le n$。

solution

二分答案

如果$a_l,a_{l+1},…, a_r$是一个长度至少为k的子数组，且中位数至少为m。要让中位数至少为m，那么子数组中大于等于m的个数减去小于m的个数的差值至少为1，无论长度奇偶性。

在$a_1,a_2,…,a_i$中，对于每个$a_r$尝试寻找合法的$a_l$，一旦找到，则说明答案至少为m。通过二分只需$O(logn)$次此过程即可得到答案。

设$x_i$为$a_1,a_2,…,a_i$中小于m的个数，$y_i$为$a_1,a_2,…,a_i$中大于等于m的个数。合法的$a_l$满足$l+k\le r, (y_r-y_{l-1})-(x_r-x_{l-1}) \ge 1\Rightarrow y_r-x_r-1\ge y_{l-1}-x_{l-1}$，显然对于$a_r$的判断只需要同时维护一个前缀最小值$mn= \min \limits_{i < r-k}y_i-x_i$，然后判断是否$y_r-x_r-1\ge mn$即可。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n+1);
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    int l = 0, r = n+1;
    while (l<r) {
        int m = l+r>>1;
        vector<int> x(n+1), y(n+1);
        for (int i=1; i<=n; i++) {
            x[i] = x[i-1];
            y[i] = y[i-1];
            if (a[i]<m) x[i]++;
            else y[i]++;
        }
        int mn = 0, ok = 0;
        for (int i=k; i<=n; i++) {
            if (y[i]-x[i]-1>=mn) {
                ok = 1;
                break;
            }
            mn = min(mn, y[i-k+1]-x[i-k+1]);
        }
        if (ok) {
            l = m+1;
        } else {
            r = m;
        }
    }
    cout << r-1 << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}