codeforces 920C【巧解】

这是一道非常简单的题，题目大意就是，给你一个从1-n的一个排列，再给你一个由0和1组成的串s，要求如果第i位出现了1 那么原先的排列中的第i个数和第i+1个数能进行交换，不限交换次数，问你最后能否使得该排列升序

一般我们的解题思路都是 我们去找连续的1存在的位置，然后给这一串数据排好序，再对处理过的串进行升序分析。
思路很简单，我们也很容易想到，而且这样的话时间复杂度也是O(nlogn)

当然对于这道题，我们还可以从另外的角度来看，我们试想一下，现在有n个数，如果中间有一段可以通过交换变成升序，那么我们可以知道对于这一段来说，第一个一定是最小的数，并且最后一个一定是最大的数，现在我们有一段区间[l,r] 如果这段序列已经升序排好，要想使得整个数列升序，我们必须满足 [1,l-1]中的最大值一定小于a[l]，[r+1,n]中的最小值，一定大于a[r]
再可以进一步说， [1，l-1]中的最大值一定小于 [l,n]中的最小值，因此我们发现，我们只要对每一个不能交换的位置进行这样的判断，我们就可以知道这个序列是否升序
最后简化为，只要求[1，i]的最大值，和[i,n]的最小值

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn=200000+50;
int a[maxn];
int mx[maxn];
int mn[maxn];
char s[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%s",&s[1]);
    mx[0]=0;
    for(int i=1;i<=n;i++)
    {
        mx[i]=max(mx[i-1],a[i]);
    }
    mn[n+1]=INF;
    for(int i=n;i>=1;i--)
    {
        mn[i]=min(mn[i+1],a[i]);
    }
    for(int i=1;i<n;i++)
    {
        if(s[i]=='1')continue;
        if(mx[i]>mn[i+1])
        {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    return 0;

}