CF2171D 题解

题目相当于判断：将所有满足

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\}

，那么

1

不可以和后面的任何数连边，否则可以连边。

在

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)

。

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;
}

文章操作

相关推荐

评论

CF2171D 题解