题目描述

难度分:$1300$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和一个$1$~$n$的排列$p$。

对于每个长度$L=1,2,3,…,n$，判断$p$是否存在一个长为$L$的连续子数组，包含$1$~$L$所有数字。

输出一个长为$n$的01字符串，依次表示$L=1,2,3,…,n$的答案，其中0表示false，1表示true。

输入样例

3
6
4 5 1 3 2 6
5
5 3 1 2 4
4
1 4 3 2

输出样例

101011
11111
1001

算法

并查集

这种题虽然分低，但还是有点思维的。最开始想的是倒着做，但是WA了之后就不知道怎么操作了，干脆还是正着来思考。从$L=1$开始考虑，这个肯定答案是true；接下来$L=2$的情况，如果它所在的位置能和$1$接起来，那肯定就是true，否则就是false。

依此类推，模拟从小到大向数组中加入数字，这些加入的数字不断合并成更大的连通块，最终变成一个大小为$n$的连通块。由于是对$L$从小到大考虑，且输入的$p$数组是个$1$到$n$的排列，没有重复元素。所以当考虑到$L=x$时，如果$x$加入后（将$x$插入在它原本位于排列$p$中的位置）能和周边的邻居合并成一个大小为$x$的连通块，那它的答案就是true，否则答案就是false。

复杂度分析

时间复杂度

线性考虑$L \in [1,n]$，时间复杂度为$O(n)$。而考虑每个$L$值的时候，有可能存在并查集的合并操作，时间复杂度为$O(logn)$。所以整个算法的时间复杂度为$O(nlogn)$。

空间复杂度

并查集的父节点数组，以及连通块大小的数组都是$O(n)$的。除此之外，还需要一个$vis$数组，一个$val2pos$数组，$vis[x]$表示$x$是否有被插入过，$val2pos[x]$表示$x$在原排列$p$中的位置，它们的空间消耗均为$O(n)$。因此，整个算法的额外空间复杂度就是$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int T, n, a[N], p[N], sz[N], vis[N], val2pos[N];

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        p[rx] = ry;
        sz[ry] += sz[rx];
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            p[i] = i;
            sz[i] = 1;
            vis[i] = 0;
            val2pos[a[i]] = i;
        }
        string s;
        for(int val = 1; val <= n; val++) {
            int i = val2pos[val];
            vis[i] = 1;
            for(int j = max(1, i - 1); j <= min(n, i + 1); j++) {
                if(vis[j] == 1) {
                    merge(j, i);
                }
            }
            if(sz[find(i)] == val) {
                s.push_back('1');
            }else {
                s.push_back('0');
            }
        }
        cout << s << endl;
    }
    return 0;
}