文章目录
题意
题目链接。
记 $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;
}
叨叨几句... NOTHING