前言

这篇题解做法简洁，其他题解菜就多练。

本题解没有使用任何数据结构，线性做法。

题目分析

首先考虑观察性质：

1. 中位数是排序后中间的数，也就是一半不严格比它小、另一半不严格比它大；
2. 考虑根据上一条性质观察终态：假设合法的中位数是 $x$，既然每个子序列都满足上一条性质那若干个子序列合起来也满足有一半小、一半大。

利用第二个性质，我们得知，最后的中位数一定是这个序列的中位数中的一个。由于要分成至少两段，这个数必须出现至少两次，所以要求这个序列有两个相同的中位数（否则无解），这样恰好规避了偶数序列两个位置的问题。

现在问题变成给定 $x$，求序列是否能分成若干段使得每段中位数都是 $x$。序列只和大小有关，可以先 $01$ 化（由于不方便，进行稍微改变，用 $-1,0,1$ 表示小于、等于、大于 $x$ 的数）。

我们继续利用刚才的性质考虑合并，假设我们存在一种分成 $t$ 段的方法，一定满足 $t$ 是偶数，否则总和不满足是偶数。由于刚才合并的性质，当 $t\ge 3$ 时我们可以随意合并 $3$ 个相邻的段，此时奇偶性不变。也就是最后一定只剩下两个段。

我们只需要枚举断点，求前后 $-1,0,1$ 的个数即可，随便用前缀和或者几个变量动态维护即可。

求、判断中位数可以用 nth_element 做到 $O(n)$，后面的维护也不需要数据结构 $O(n)$。

所以时间复杂度是 $O(n)$。

代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=2e5+1;
int n,a[N],tmp[N],x,y,sum1,sum_1,suf1,suf_1,pre1,pre_1;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        tmp[i]=a[i];
    }
    nth_element(tmp+1,tmp+(n/2),tmp+n+1);
    x=tmp[n/2];
    nth_element(tmp+1,tmp+(n/2)+1,tmp+n+1);
    y=tmp[(n/2)+1];//求中位数
    if(x!=y){
        cout<<"No";
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(a[i]<x)
            a[i]=-1,sum_1++;
        else if(a[i]>x)
            a[i]=1,sum1++;
        else
            a[i]=0;
    }//变为 -1 0 1
    suf1=sum1,suf_1=sum_1;//记录个数
    for(int i=1,pre0,suf0;i<n;i++){
        if(a[i]<0)
            suf_1--,pre_1++;
        else if(a[i]>0)
            suf1--,pre1++;
        if(i&1){
            pre0=i-(pre1+pre_1);
            suf0=(n-i)-(suf1+suf_1);
            if(pre_1<(i+1)/2&&(i+1)/2<=i-pre1&&suf_1<(n-i+1)/2&&(n-i+1)/2<=(n-i)-suf1){
                cout<<"Yes";//判断合法
                return 0;
            }
        }
    }
    cout<<"No";
    return 0;
}