题解：P17143 [NOI 2026] 中位数

· · 题解

场外 vp 选手，这是六题里面唯一会的一道。

做法稍微有点诡异，如果假了告诉我。

看到神秘中位数考虑先二分一步，然后把 \ge mid 设为 1 否则设为 -1，我们只需要判断能否划分成 k 段使得有 \ge \lceil \frac{k}2\rceil 段的和 \ge 0。

有一种暴力想法是我们直接设 f_{i,j} 表示考虑到 i，一共选了 j 段，最多选出多少个 \ge 0 的段，可以树状数组优化 dp 做到总复杂度 O(nk \log^2 n)。

然后它在 qoj 上得了整整 70 分，吓哭了。

感觉特别能做，考虑继续做。观察到部分分里有 k>5 和 k 是偶数之类的，特别反常，猜测 k 大的时候有一种通用的方法解决，且需要分奇偶性讨论。

于是我们想想二分之后有没有什么智慧一些的 check 方法，发现有一种想法是我们把每个 1 都单独划分一个连续段，好像很优啊！再观察一下，发现 1 的数量小于 \lceil \frac{k}2\rceil 的时候显然无解（你要凑出这么多大于等于 0 的段，每个段至少有一个 1），但是大于等于却不一定存在解，根本原因在于其它的段落可能无法划分在 \lfloor \frac{k}2 \rfloor 之内，导致我们“恰好划分 k 段”的条件不满足。

但是再观察，发现这个时候其它的段落数最多是 1 的数量加一（用 1 把它们隔开），又因为如果 1 的数量比 \lceil \frac{k}2\rceil 大，我们可以直接把 1 扔到 -1 段里面，通过后面的过程可以看出这种操作（几乎）不会影响有无解，所以我们只需要使得 1 的数量比 -1 连续段的数量在 k 奇数的时候大，在 k 偶数的时候大于等于即可。

稍微想一下，刚才的那个把 1 扔到 -1 段里面的操作，在 k\le 5 的时候会出问题，k>5 的时候才可以这样做，这时我们就理解了部分分的用意。

判掉 1 的数量已经大于等于 -1 段的情况，剩下的就是我们需要修的，仔细想想有哪些情况我们可能要修，两对 1 贴贴（可以有公用 1）的情况出现两次一定有解，一对 1 贴贴的情况出现一次且 k 是偶数的时候也有解，剩下我们发现情况很少，只剩下 k 是奇数且一对 1 贴贴或者没有 1 贴贴的情况，能改成有解的话最多只需要让我们删掉两个 -1 段，于是直接开始贪心，尝试将长度为 1 的 -1 段优先分给左边的 1，不行再给右边；长度为 2 的 -1 段尝试让两边一人一个，特判首尾。这样就可以完成所有情况的判断。

顺带说一下，刚才的 k\le 5 会出问题的情况中的一种就是有两对 1 贴贴的情况，当 k\le 6 的时候就会开始需要动这两对，但是 6 是偶数恰好不会影响判断。

但是这样在 k\le 5 的时候还是 O(nk\log^2 n) 比较死亡，不过 qoj 直接就过了。优化的话可以考虑把这个选的段数也加入到状态里，然后把状态存的值改成当前段的最大和，可以做到 O(nk^2\log n)，视此时的 k 为常数，总时间复杂度 O(n\log n)。

代码写的极其抽象，还没有上面说的清楚，不建议任何人观看。

::::success[代码]

#include<bits/stdc++.h>
#include "median.h"
#define N 1000005
using namespace std;
int b[N],nn,kk,d[N],s[N],f[N],lst[N];
struct BIT{
    int c[N*2];
    void clear(){
        for(int i=1;i<=nn*2+1;++i)c[i]=-1e9;
    }
    void add(int x,int k){
        x+=nn+1;
        while(x<=nn*2+1)c[x]=max(c[x],k),x+=x&-x;
    }
    int ask(int x){
        x+=nn+1;
        int ans=-1e9;
        while(x)ans=max(ans,c[x]),x-=x&-x;
        return ans;
    }
}A; 
void init(int c,int t){

}
bool check(int mid){ 
    for(int i=1;i<=nn;++i){
        if(b[i]>=mid)d[i]=1;
        else d[i]=-1;
        s[i]=s[i-1]+d[i];
    }
    if(kk<=5){
        for(int i=1;i<=nn;++i)lst[i]=-1e9;
        lst[0]=0;
        for(int i=1;i<=kk;++i){
            A.clear();
            int mx=0;
            A.add(0,0);
            for(int j=1;j<=nn;++j){
                f[j]=max(mx,A.ask(s[j])+1);
                A.add(s[j],lst[j]);
                mx=max(mx,lst[j]);
            }
            for(int j=1;j<=nn;++j)lst[j]=f[j];
        }
        return f[nn]>=(kk+1)/2;
    }
    else{
        int cnt1=0,df=0,l=0;
        for(int i=1;i<=nn;++i){
            if(d[i]==-1)l=1;
            else{
                if(l)++df,l=0;
                ++cnt1;
            }
        }
        if(l)++df;
    //  if(mid==71){
    //      for(int i=1;i<=nn;++i)cout<<d[i]<<" ";cout<<'\n';
    //      cout<<cnt1<<" "<<df<<'\n';
    //  }  
        if(cnt1<(kk+1)/2)return 0;
        int ly=0;
        for(int i=1;i<nn;++i){
            if(d[i]==1&&d[i+1]==1)++ly;
        }
        if(ly>=2)return 1;
        if(ly==1&&kk%2==0)return 1;
        if(kk%2&&cnt1>df||kk%2==0&&cnt1>=df)return 1;
        //if(mid==71)cout<<"qwq\n"; 
        l=0;int lst=0,fzj=0,o=-1;
        for(int i=1;i<=nn;++i){
            if(d[i]==-1)++l;
            else{
                if(l&&(!lst&&l==1||lst&&l<=2)){
                    if(lst&&l==1){
                        if(o==lst)o=i;
                        else o=lst;
                        ++fzj;
                    }
                    else if(o!=lst){
                        ++fzj;
                        o=i;
                    }
                }
                l=0;
                lst=i;
            }
        }
        if(l==1&&lst!=o)++fzj;
        df-=fzj;
        if(kk%2&&cnt1>df||kk%2==0&&cnt1>=df)return 1;
        return 0;
    }
}
int median(int n,int k,vector<int>a){
    nn=n;kk=k;
    for(int i=1;i<=n;++i)b[i]=a[i-1];
    int l=1,r=n,ans;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
/*
10:22 start
0 1
80 10
42 2 11 20 37 46 33 59 31 60 32 5 49 43 14 61 6 47 51 15 12 57 18 26 34 75 67 36 52 53 8 16 68 7 39 56 74 1 29 44 70 65 4 27 78 24 45 38 73 50 35 62 72 21 63 55 69 10 9 41 76 64 22 19 77 3 30 13 80 28 48 40 71 23 54 58 79 25 66 17
*/