时间复杂度O（nlog2(n)） 当题目限制取消全局上下界就ok(来源GTAlgorithm)

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N],b[N];
int n;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    string str;cin>>str;
    int l=0,r=0;
    while(l<n-1)
    {
        while(l<n-1&&str[l]=='0')l++;
        if(l>=n-1)break;
        r=l;
        while(r<n-1&&str[r]=='1')r++;
        sort(a+l,a+r+1);//'1111..11'+'0'  (相邻的那个零也参与排序)
        l=r;
    }
    if(is_sorted(a,a+n))puts("YES");
    else puts("NO");
    return 0;
}

时间复杂度O(n)(来源y总视频)

a: 1->n b :1->n 如果b [pos]=0并且1->pos-1可以有序 ; 那么只要max(b[1],b[2]…b[pos])=pos, 1->pos就有序,因为所有数字从都在1–n之间（有明确的全局上下界），并且互相不重复 ，所以每个0的位置都对应一个明确上界

#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e+5;
int n;
int a[N];
char str[N];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    cin>>str+1;
    bool flag=true;
    for(int i=1,t=0;i<=n;i++)
    {
         t=max(t,a[i-1]);
         if(str[i]=='0'&&i!=t)flag=false;
    }
    if(flag) puts("YES");
    else puts("NO");
    return 0;
}