只有我没去青岛……

非常有意思的一道推性质题。看到“最大化‘中位数的中位数’”直接触发关键词第一反应肯定就是二分答案啦。所以我们只需考虑 check() 怎么写。

假设我们当前二分的值为 $x$。经典套路，对原数组进行二值化：令 $a_i \ge x$ 的位置 $w_i = 1$，$a_i < x$ 的位置 $w_i = -1$。

考虑划分出的某一个连续段，假设其中有 $h$ 个 $1$ 和 $d$ 个 $-1$。这一段的中位数 $\ge x$，当且仅当 $1$ 的数量占绝对优势，即：

$$h \ge \left\lceil\frac{h+d}{2}\right\rceil \iff h \ge d$$

换句话说，这一段的二值和 $\ge 0$。为了方便，我们称二值和 $\ge 0$ 的段为好段。

最终我们要让 $k$ 个中位数的中位数 $\ge x$，这等价于这 $k$ 个段中，至少要有 $q = \left\lceil\frac{k}{2}\right\rceil$ 个好段。剩下随便乱分的段数为 $r = \left\lfloor\frac{k}{2}\right\rfloor = k - q$。

于是问题就转化为了：判断能否在序列里选出 $q$ 个互不相交的好段，并且剩下的元素能刚好划分成 $r$ 个非空段。

选出 $q$ 个好段后，它们之间连带序列两端，一共会产生 $q+1$ 个“空隙”。因为最终还要凑 $r$ 个普通段，每个非空空隙至少得塞进去一个普通段，所以非空空隙的数量绝对不能超过 $r$。反过来说，这 $q+1$ 个空隙里，至少要有 $d = q+1-r$ 个空隙是完全空的。

然后我们注意到简单计算一下就能发现：

• 当 $k$ 是偶数时，$d = 1$；
• 当 $k$ 是奇数时，$d = 2$。

“空隙为空”在物理意义上对应着三种边界事件：

1. L：一个好段紧贴着序列的最左端开始；
2. R：一个好段紧贴着序列的最右端结束；
3. I：两个好段首尾相接（内部相邻）。

由于最多只需要 $2$ 个事件，这启发我们只需枚举常数种局部结构即可。

如果每次都要判断方案是否合法，我们需要一个统一的标准。设整个序列里共有 $pc$ 个 $1$。除了那些用来制造“空隙事件”的特殊好段外，剩下的好段我们显然希望它们越短越好。显然最短就是直接拿一个值为 $1$ 的单点当好段。

考虑某个包含 $t$ 个好段的局部结构，设它的总长度是 $len$，内部二值和为 $sum$。

这个结构里面实际包含的 $1$ 的数量是 $\frac{len+sum}{2}$。

比起直接用 $t$ 个正数单点，这个局部结构额外占用了：

• $len-t$ 的长度；
• $\frac{len+sum}{2}-t$ 个 $1$。

全局来看，我们能“挥霍”的最多剩余长度是 $z = n-k$，能“挥霍”的最多额外 $1$ 的数量是 $u = pc-q$。

因此，一个局部结构合法，当且仅当满足以下三个限制条件：

1. $t \le q$；
2. $len-t \le z$；
3. $\frac{len+sum}{2}-t \le u$。

如何优雅地寻找最优好段？

设二值化后的前缀和为 $p$。区间 $[l, r)$ 是好段等价于 $p_r \ge p_l$。

对于从 $i$ 开始的最短好段，如果 $w_i=1$，显然最短就是 $[i, i+1)$；如果 $w_i=-1$，那就必须等到前缀和第一次回升到 $p_i$，也就是找到最小的 $j > i$ 满足 $p_j = p_i$。我们将这个终点记为 $ng(i)$。

同理，我们也能求出以 $i$ 结尾的最短好段起点，记为 $lf(i)$。

当我们需要找两个相邻的好段，设它们的公共分界点为 $m$ 时，最优解一定左边取 $[lf(m), m)$，右边取 $[m, ng(m))$。

为什么？因为你让左右两边独立往分界点 $m$ 收缩，既不会破坏它们相邻的性质，又会同时减少它们占用的长度和 $1$ 的个数，所以固定分界点后这样选必定是最优（支配）的。

同理，对于三个相邻好段，只要枚举其中一个分界点建出两个最短好段，然后在左边或右边再紧贴着补一个最短好段即可。

现在我们要枚举的结构就很清晰了。我们定义：

• L1、R1：单端点贴边；
• I2：两个好段相邻；
• L2、R2：贴边且包含两个相邻好段；
• I3：三个好段相邻。

1. 当 $k$ 为偶数时

   只需要 $1$ 个事件。直接枚举校验 L1，R1，以及所有的 I2 结构即可。

2. 当 $k$ 为奇数时

   需要 $2$ 个事件。这两事件可能是一个连通的整体，也可能互不相交。

   • 整体结构：枚举校验 L2，R2，I3。
   • 不相交结构：L1+R1，L1+I2，I2+R1，I2+I2。

这里面唯一需要点小技巧的是 I2+I2。因为每个最短好段的和只能是 $0$ 或者是 $1$，所以一个 I2 的总和只有可能是 $0, 1, 2$。

我们在顺序枚举第二个 I2 时，顺便维护一下前面已经结束的第一个 I2 中，总和分别为 $0, 1, 2$ 的最小长度，这样就能在 $\mathcal{O}(n)$ 内完成 I2+I2 的配对。

复杂度分析

对于每次 check(x)：

• 跑一面前缀和并处理 $ng(i)$ 和 $lf(i)$：$\mathcal{O}(n)$；
• 枚举常数种局部结构，并做 I2+I2 配对：$\mathcal{O}(n)$。

单次 check 是严格 $\mathcal{O}(n)$。外面套一个二分答案，总体时间复杂度为 $\mathcal{O}(n \log n)$。

Code

本 code 已过 qoj。

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

const int M = 1000005;
const int V = 2000015;
const int inf = 0x3f3f3f3f;
int p[M], nx[M], pv[M];
int ls[V];
int le[M], ri[M], sv[M];
int he[M], hs[M], ae[M], as[M];

void init(int c, int t)
{
}

int ng(int x, int n)
{
    if (x < 0 || x >= n)
    {
        return -1;
    }
    return nx[x];
}

int lf(int x)
{
    if (x <= 0)
    {
        return -1;
    }
    if (p[x] - p[x - 1] == 1)
    {
        return x - 1;
    }
    return pv[x];
}

int fit(int len, int sum, int t, int z, int u, int q)
{
    if (t > q)
    {
        return 0;
    }
    if (len - t > z)
    {
        return 0;
    }
    if ((len + sum) / 2 - t > u)
    {
        return 0;
    }
    return 1;
}

int check(int n, int k, vector<int> &a, int x)
{
    int pc = 0;
    int mn = 0;
    int mx = 0;
    p[0] = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] >= x)
        {
            p[i + 1] = p[i] + 1;
            pc++;
        }
        else
        {
            p[i + 1] = p[i] - 1;
        }
        mn = min(mn, p[i + 1]);
        mx = max(mx, p[i + 1]);
    }
    int q = (k + 1) / 2;
    if (pc < q)
    {
        return 0;
    }
    int z = n - k;
    int u = pc - q;
    int o = n + 1;
    for (int i = mn + o; i <= mx + o; i++)
    {
        ls[i] = -1;
    }
    for (int i = 0; i <= n; i++)
    {
        pv[i] = ls[p[i] + o];
        ls[p[i] + o] = i;
    }
    for (int i = mn + o; i <= mx + o; i++)
    {
        ls[i] = -1;
    }
    for (int i = n; i >= 0; i--)
    {
        int j = ls[p[i] + o];
        if (i < n)
        {
            if (p[i + 1] - p[i] == 1)
            {
                nx[i] = i + 1;
            }
            else
            {
                nx[i] = j;
            }
        }
        ls[p[i] + o] = i;
    }
    for (int i = 0; i <= n; i++)
    {
        he[i] = -1;
        hs[i] = -1;
    }
    for (int m = 1; m < n; m++)
    {
        le[m] = lf(m);
        ri[m] = ng(m, n);
        if (le[m] >= 0 && ri[m] >= 0)
        {
            sv[m] = p[ri[m]] - p[le[m]];
            ae[m] = he[ri[m]];
            he[ri[m]] = m;
            as[m] = hs[le[m]];
            hs[le[m]] = m;
        }
    }
    int l1 = ng(0, n);
    int r1 = lf(n);
    if (k % 2 == 0)
    {
        if (l1 >= 0 && fit(l1, p[l1], 1, z, u, q))
        {
            return 1;
        }
        if (r1 >= 0 && fit(n - r1, p[n] - p[r1], 1, z, u, q))
        {
            return 1;
        }
        if (q >= 2)
        {
            for (int m = 1; m < n; m++)
            {
                if (le[m] >= 0 && ri[m] >= 0)
                {
                    int len = ri[m] - le[m];
                    if (fit(len, sv[m], 2, z, u, q))
                    {
                        return 1;
                    }
                }
            }
        }
        return 0;
    }
    if (q >= 2)
    {
        for (int m = 1; m < n; m++)
        {
            int r = ng(m, n);
            if (p[m] >= p[0] && r >= 0)
            {
                if (fit(r, p[r], 2, z, u, q))
                {
                    return 1;
                }
            }
            int l = lf(m);
            if (l >= 0 && p[n] >= p[m])
            {
                if (fit(n - l, p[n] - p[l], 2, z, u, q))
                {
                    return 1;
                }
            }
        }
    }
    if (l1 >= 0 && r1 >= 0 && l1 <= r1)
    {
        int len = l1 + n - r1;
        int sum = p[l1] + p[n] - p[r1];
        if (fit(len, sum, 2, z, u, q))
        {
            return 1;
        }
    }
    for (int m = 1; m < n; m++)
    {
        if (le[m] < 0 || ri[m] < 0)
        {
            continue;
        }
        int len = ri[m] - le[m];
        int sum = sv[m];
        if (l1 >= 0 && l1 <= le[m])
        {
            if (fit(l1 + len, p[l1] + sum, 3, z, u, q))
            {
                return 1;
            }
        }
        if (r1 >= 0 && ri[m] <= r1)
        {
            if (fit(len + n - r1, sum + p[n] - p[r1], 3, z, u, q))
            {
                return 1;
            }
        }
        int l = lf(le[m]);
        if (l >= 0)
        {
            if (fit(ri[m] - l, p[ri[m]] - p[l], 3, z, u, q))
            {
                return 1;
            }
        }
        int r = ng(ri[m], n);
        if (r >= 0)
        {
            if (fit(r - le[m], p[r] - p[le[m]], 3, z, u, q))
            {
                return 1;
            }
        }
    }
    if (q >= 4)
    {
        int bl[3] = {inf, inf, inf};
        for (int i = 0; i <= n; i++)
        {
            for (int m = he[i]; m >= 0; m = ae[m])
            {
                int len = ri[m] - le[m];
                bl[sv[m]] = min(bl[sv[m]], len);
            }
            for (int m = hs[i]; m >= 0; m = as[m])
            {
                int len = ri[m] - le[m];
                for (int s = 0; s <= 2; s++)
                {
                    if (bl[s] < inf && fit(bl[s] + len, s + sv[m], 4, z, u, q))
                    {
                        return 1;
                    }
                }
            }
        }
    }
    return 0;
}

int median(int n, int k, vector<int> a)
{
    int l = 1;
    int r = n;
    while (l < r)
    {
        int m = (l + r + 1) / 2;
        if (check(n, k, a, m))
        {
            l = m;
        }
        else
        {
            r = m - 1;
        }
    }
    return l;
}