中位数 NOI 2026

[NOI 2026] 中位数

我声称摩卡串是简单好写好想题。

题目链接： [NOI 2026] 中位数 。

题目描述：

把长度为 $n$ 的序列切成 $k$ 段，要求每段中位数构成的序列的中位数最大。

$5\le n \le 10^6,2\le k \le n$ 。

中位数的定义：长度为 $m$ 的序列的中位数为第 $\lceil\frac{m}{2}\rceil$ 大的数。

警示后人：

性质 $\text{A}$ ， $k\bmod 2\equiv 0$ 和 $k>5$ 是诈骗性质。

这个题目就是让你冲正解的，几乎没有部分分。

经典二分转 $1,-1$ 序列 $b$ 。

那么一个序列的中位数 $\ge x$ 的充要条件为序列的和 $\ge 0$ 。

现在问题变成了：判定一个 $-1,1$ 的序列 $b$ 是否能切成 $k$ 份使得至少有 $\lceil\frac{k}{2}\rceil$ 个子区间的和 $\ge 0$ 。

首先，我们有一个显然的构造：选取 $\lceil\frac{k}{2}\rceil$ 个 $1$ 单独成一个子区间，然后序列就会断成 $k+(k\bmod 2)+1$ 个区间。

接着我们就要根据 $k\bmod 2$ 分类讨论：

Case #1 : $k\bmod 2=0$

此时我们需要删除一个区间。

考虑什么情况下我们可以删除区间。

由于序列能断成 $k+(k\bmod 2)+1$ 个区间的时候，他的样子应该是：

$$01010101010101010\cdots0101010101010101010101010$$

那么我们就有三种方式删除区间：

1. 让开头变为 $1$ ，即 $\textcolor{red}{1}0101010\cdots010101010$ 。
2. 让结尾变为 $1$ ，即 $010101010\cdots0101010\textcolor{red}{1}$ 。
3. 让中间两个 $1$ 相邻，即 $0101010\cdots01010\textcolor{red}{11}010101\cdots0101010$ 。

接下来考虑如何处理这三种情况。

首先第一第二种是容易的，只需要枚举一个前后缀，然后判断剩余区间的 $1$ 的个数是否合法就行。

然后就是第三种。这种情况下我们可以枚举一个 $i$ ，预处理出 $pos_i$ 表示最大的满足 $[pos_i,i]$ 的和 $\ge 0$ 的数， $pos2_i$ 表示最小的满足 $[i,pos2_i]$ 的和 $\ge 0$ 的数。用 $pos_i$ 和 $pos2_{i+1}$ 转移就行。

问题是如何线性预处理 $pos,pos2$ 。

以 $pos$ 举例。

理论上，我们为了处理这个，需要整一个值域数组，每次单点修改，以及查询一个后缀的最大值。这似乎只能 $O(\log n)$ 做。但是，这是一个 $-1,1$ 序列。这也就意味着，对于某一个 $i$ ，若 $b_i=1$ ，则 $pos_i=i$ ，否则必然有 $[pos_i,i]$ 的和为 $0$ 。此时就是一个单点修改，单点查询，一个桶搞定。

Case #2 : $k\bmod 2=1$

此时要删两个区间。

那么，将 Case #1 的三种删除区间的方法组合以下，可以得到以下七种：

1. 两端都是 $1$ ，即 $\textcolor{red}{1}01010\cdots0101010\textcolor{red}{1}$ 。
2. 开头的连续两个 $1$ ，即 $\textcolor{red}{11}01010\cdots010101010$ 。
3. 结尾的连续两个 $1$ ，即 $010101010\cdots01010\textcolor{red}{11}$ 。
4. 开头一个 $1$ ，中间连续两个 $1$ ，即 $\textcolor{red}{1}0101010\cdots01010\textcolor{red}{11}010101\cdots0101010$ 。
5. 结尾一个 $1$ ，中间连续两个 $1$ ，即 $0101010\cdots01010\textcolor{red}{11}010101\cdots0101010\textcolor{red}{1}$ 。
6. 中间连续 $3$ 个 $1$ ，即 $0101010\cdots01010\textcolor{red}{111}010101\cdots0101010$ 。
7. 两个无交的连续的两个 $1$ ，即 $0101010\cdots01010\textcolor{red}{11}010101\cdots01010\textcolor{red}{11}010101\cdots0101010$ 。

前 $5$ 种利用 $pos,pos2$ 容易转移。

第 $7$ 种利用一个辅助数组也可以轻松转移。

主要是第 $6$ 种。

首先一个直观的想法是枚举 $i$ ，然后令三个区间分别为 $[pos_{pos_i-1},pos_i-1][pos_i,i][i+1,pos2_{i+1}]$ 。

然而这是错的。

举一个例子， $100101$ ，有一个显然的划分为 $(10)(01)(01)$ ，但是如果套用刚才的那个算法就会挂掉。这是因为最短的 $\ge 0$ 的区间的另一个端点不一定也有对应的 $\ge 0$ 的区间。换句话说，也就是，可能 $pos_{pos_i-1}$ 不存在但是存在一个更小的 $q$ 满足 $[pos_{q-1},q-1][q,i]$ 合法。

解决它也十分简单。令 $p_i$ 为最大的满足 $[p,i]$ 的和恰好为 $0$ 的数。那么枚举 $i$ ，令三个区间先分别为 $[pos_{pos_i-1},pos_i-1][pos_i,i][i+1,pos2_{i+1}]$ ，再分别为 $[pos_{p_i-1},p_i-1][p_i,i][i+1,pos2_{i+1}]$ 。

原因十分简单，如果存在一个更小的 $q$ 满足 $q<p_i$ 且 $pos_{q-1}$ 存在且 $pos_{p_i-1}$ 不存在，不妨设 $p_i<pos_i$ ，那么必然有 $[q,i]$ 的和为 $0$ 。又因为 $[p,i]$ 的和也为 $0$ ，所以 $[q,p-1]$ 的和为 $0$ ，也就是说， $p_i$ 必然存在且至少为 $q$ ，矛盾，所以原假设不成立，考虑 $pos_i$ 和 $p_i$ 可以涵盖所有情况。

以上是整个题目最难的部分（不是就这？），大力出奇迹的分类讨论就行。

代码：

#include <bits/stdc++.h>
#include "median.h"
using namespace std;
#define WZH
#ifdef WZH
#ifndef MEDIAN_H
void init(int c, int t);
int median(int n, int k, std::vector<int> a);
#endif
#endif
using V=vector<int>;
bool check(V &a,int x,int k){
    int n=a.size(),aim=(k+1)>>1;
    V b(n+1,0),s(n+1,0),S(n+1,0);
    for(int i=1;i<=n;i++)b[i]=(a[i-1]>=x?1:-1);
    for(int i=1;i<=n;i++)s[i]=s[i-1]+b[i],S[i]=S[i-1]+(b[i]==1);
    if(S[n]<aim)return 0;
    V cl(n*2+1,0),cl2(n*2+1,0),pos(n+1,0),pos2(n+1,0),p(n+1,0),pp(n+1,n+1);
    for(int i=1;i<=n;i++){
        if(b[i]==1)pos[i]=i;
        else pos[i]=cl[n+s[i]];
        p[i]=cl[n+s[i]];
        cl[n+s[i]]=i+1;
    }
    for(int i=n;i>=1;i--){
        if(b[i]==1)pos2[i]=i;
        else pos2[i]=cl2[n+s[n]-s[i-1]];
        cl2[n+s[n]-s[i-1]]=i-1;
    }
    if(k&1){
        int st=0,ed=0;
        for(int i=1;i<=n;i++)if(s[i]>=0){st=i;break;}
        for(int i=n;i>=1;i--)if(s[n]-s[i-1]>=0){ed=i;break;}
        if(st&&ed&&ed-st-1>=k-2&&S[ed-1]-S[st]>=aim-2)return 1;
        for(int i=1;i<n;i++){
            if(pos2[i+1]&&s[i]>=0&&n-pos2[i+1]>=k-2&&S[n]-S[pos2[i+1]]>=aim-2)
                return 1;
        }
        for(int i=2;i<=n;i++){
            if(pos[i-1]&&s[n]-s[i-1]>=0&&pos[i-1]-1>=k-2&&S[pos[i-1]-1]>=aim-2)
                return 1;
        }
        if(k==3)return 0;
        for(int i=1;i<n;i++){
            if(!pos[i]||!pos2[i+1])continue;
            if(st&&pos[i]>st&&pos[i]-1-st+(n-pos2[i+1])>=k-3&&
                S[pos[i]-1]-S[st]+(S[n]-S[pos2[i+1]])>=aim-3)
                    return 1;
            if(ed&&pos2[i+1]<ed&&ed-1-pos2[i+1]+(pos[i]-1)>=k-3&&
                S[pos[i]-1]+(S[ed-1]-S[pos2[i+1]])>=aim-3)
                    return 1;
        }
        for(int i=2;i<n;i++){
            int z=pos2[i+1],y=p[i];
            if(!y||!z)continue;
            int x=pos[y-1];
            if(!x)continue;
            if(x-1+n-z>=k-3&&S[x-1]+S[n]-S[z]>=aim-3)return 1;
        }
        for(int i=2;i<n;i++){
            int z=pos2[i+1],y=pos[i];
            if(!y||!z)continue;
            int x=pos[y-1];
            if(!x)continue;
            if(x-1+n-z>=k-3&&S[x-1]+S[n]-S[z]>=aim-3)return 1;
        }
        if(k==5)return 0;
        for(int i=1;i<n;i++){
            pp[i]=min(pp[i],pp[i-1]);
            if(!pos[i]||!pos2[i+1])continue;
            if(pp[pos[i]-1]<=pos[i]-1){
                if(S[pos[i]-1]-pp[pos[i]-1]+S[n]-S[pos2[i+1]]>=aim-4)
                    return 1;
            }
            pp[pos2[i+1]]=min(pp[pos2[i+1]],S[pos2[i+1]]-S[pos[i]-1]);
        }
        return 0;
    }
    else{
        for(int i=1;i<=n-k+1;i++)if(s[i]>=0&&S[n]-S[i]>=aim-1)return 1;
        for(int i=k-1;i<n;i++)if(s[n]-s[i]>=0&&S[i]>=aim-1)return 1;
        if(k==2)return 0;
        for(int i=1;i<n;i++){
            if(pos[i]&&pos2[i+1]&&pos[i]-1+n-pos2[i+1]>=k-2&&
                S[pos[i]-1]+S[n]-S[pos2[i+1]]>=aim-2)
                    return 1;
        }
        return 0;
    }
}
void init(int c,int t){}
int median(int n,int k,V a){
    int l=1,r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(a,mid,k))l=mid;
        else r=mid-1;
    }
    return l;
}