题意

题目链接。

记 $b_i$ 为 $a_1 \sim a_{2i-1}$ 的中位数，给定序列 $b$，询问是否存在合法的序列 $a$。

解析

考虑 $b_i$ 和 $b_{i-1}$ 的关系。我们先假设 $b_1 \sim b_{i-1}$ 均合法。

• 若 $b_{i-1}=b_i$，则新增的两个数只需一大一小地取即可，$b_i$ 也一定合法。
• 若 $b_{i-1}<b_i$，因为 $b_{i-1}$ 是 $2i-3$ 个数的中位数，所以序列中一定有 $i-1$ 个数比 $b_i$ 小。对于任意一个 $b_j(j<i-1)$ ，如果其满足 $b_j \le b_{i-1}$，则它可以作为这 $i-1$ 个数中的一个数，不影响结果。若其满足 $b_{i-1} < b_j < b_i$，则此时我们发现序列中至少有 $i$ 个数比 $b_i$ 小，这就是不合法的。
• 若 $b_{i-1}>b_i$，同理寻找有无一个 $b_j$ 满足 $b_{i-1}>b_j>b_i$ 即可。

我们发现所有相同的数出现一次和出现多次在统计答案时没有区别，因为可以简单地使用一个 set 维护，每次查询时：

• 若 $b_{i-1}<b_i$，查询 $b_{i-1}$ 的后继是否为 $b_i$，若不是则不存在合法序列 $a$。
• 若 $b_{i-1}>b_i$，查询 $b_i$ 的后继是否为 $b_{i-1}$。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n;
int b[N];
set<int> s;
int main(){
    scanf("%d",&T);
    while(T--){
        bool fl=1;
        s.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            if(!s.count(b[i])) s.insert(b[i]);//相同的数无意义，直接不加入 set 即可。
            if(b[i]==b[i-1]) continue;
            if(b[i-1]<b[i]){
                if(s.upper_bound(b[i-1])!=s.find(b[i])){
                    fl=0;//若 b[i-1] 的后继不为 b[i]，就不合法。
                }
            }
            else{
                if(s.upper_bound(b[i])!=s.find(b[i-1])){
                    fl=0;//同理
                }
            }
        }
        if(fl){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}