题目描述

难度分:$1400$

输入$n(1 \leq n \leq 3 \times 10^5)$和一个$1$~$n$的排列$a$，然后输入一个长为$n-1$的01字符串$s$。

$s[i]=1$表示你可以交换$a[i]$和$a[i+1]$（交换次数不限），$s[i]=0$表示不能交换$a[i]$和$a[i+1]$。

判断能否把 a 变成递增的。输出YES或NO。

输入样例$1$

6
1 2 5 3 4 6
01110

输出样例$1$

YES

输入样例$2$

6
1 2 5 3 4 6
01010

输出样例$2$

NO

算法

排序

分析一下可以发现性质，交换相邻项是我们将数组变为有序的唯一手段，而这个交换操作会被0给阻断。假设$[l,r]$子串是一段连续的1，那么子数组$[l,r+1]$就可以通过邻项交换变为有序。

因此我们可以将所有连续1对应的子数组排序，如果排完之后$a$是有序的，就输出YES，否则输出NO。

复杂度分析

时间复杂度

本质上其实就是对数组排序，在最差情况下是对整个数组排序，时间复杂度为$O(nlog_2n)$。

空间复杂度

排序的额外空间复杂度可以看成快排的空间复杂度，为$O(log_2n)$（堆排序的话可以到$O(1)$）。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 300010;
char s[N];
int n, a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%s", s + 1);
    int left = 0, right = 0;
    for(int i = 1; i <= n; i++) {
        if(s[i] == '1') {
            if(right == 0) {
                left = right = i;
            }else {
                right++;
            }
        }else {
            sort(a + left, a + min(n, right + 1) + 1);
            left = right = 0;
        }
    }
    if(left > 0) {
        sort(a + left, a + min(n, right + 1) + 1);
    }
    if(is_sorted(a + 1, a + n + 1)) puts("YES");
    else puts("NO");
    return 0;
}