CF2171D 题解
MCHEYH
·
·
题解
题目相当于判断：将所有满足 u<v 且 p_u<p_v 的 u 和 v 连边，最后所有点是否在同一个连通块中。
我们把 p_1\sim p_n 分成两个部分 A,B，一开始，A 里面没有数，B 里面有所有数。
然后，我们从 p_1 到 p_n 不断地将 p_i 从 B 中移除，加入到 A 中。
在 $i=1$ 时可以连边： $p_1<\max\{B\}$ 的前提下，$i=2$ 时，如果 $\min\{p_1,p_2\}>\max\{B\}$，说明 $p_1<p_2$ 且 $p_2$ 为 $2\sim n$ 中 $p_i$ 的最大值，那么 $p_2$ 不可能和后面的点连边。
以此类推，我们只要不断比较 $\min\{A\}$ 和 $\max\{B\}$ 即可。时间复杂度 $O(n\log n)$。
::::success[AC Code]
```cpp
#include <iostream>
#include <set>
using namespace std;
const int maxn = 2e5+5;
int t,n,a[maxn];
set<int>S1,S2;
int main(){
cin >> t;
while(t--){
cin >> n;
S1.clear();S2.clear();
for(int i = 1;i<=n;i++){
cin >> a[i]; S2.insert(a[i]);
}
bool flag=true;
for(int i = 1;i<n;i++){
S1.insert(a[i]); S2.erase(a[i]);
if(*S1.begin() > *S2.rbegin()){
flag = false;break;
}
}
if(flag)cout<<"Yes\n"; else cout <<"No\n";
}
return 0;
}
```
::::