Beautiful Numbers

题意翻译

### 题意简述 你得到了正整数 $1$ 到 $n$ 的一个排列 $p=[p_1,p_2,···,p_n]$。 我们称数字 $m(1 \leq m \leq n)$ 是美丽的，当且仅当存在两个正整数 $l,r(1\leq l\leq r \leq n)$， 使得 $p_l,p_{l+1},\cdots,p_r$ 是正整数 $1$ 到 $m$ 的一个排列。 对于所有的 $m$，您需要求出其是否是美丽的。 ### 输入格式 第一行一个正整数 $t(1\leq t \leq 1000)$，表示数据组数。 对于每组数据，第一行是一个正整数 $n(n \leq 2·10^5)$。 接下来一行 $n$ 个正整数 $p_1,p_2,···,p_n$ ，是正整数 $1$ 到 $n$ 的一个排列。 保证输入的 $n$ 之和不超过 $2·10^5$。 ### 输出格式 对于每组数据输出一个长度为 $n$ 的 $01$ 字符串。如果当 $m=i$ 时 $m$ 是美丽的，则字符串的第 $i$ 位是 $1$，否则是 $0$。 翻译贡献者 U108949

题目描述

You are given a permutation $ p=[p_1, p_2, \ldots, p_n] $ of integers from $ 1 $ to $ n $ . Let's call the number $ m $ ( $ 1 \le m \le n $ ) beautiful, if there exists two indices $ l, r $ ( $ 1 \le l \le r \le n $ ), such that the numbers $ [p_l, p_{l+1}, \ldots, p_r] $ is a permutation of numbers $ 1, 2, \ldots, m $ . For example, let $ p = [4, 5, 1, 3, 2, 6] $ . In this case, the numbers $ 1, 3, 5, 6 $ are beautiful and $ 2, 4 $ are not. It is because: - if $ l = 3 $ and $ r = 3 $ we will have a permutation $ [1] $ for $ m = 1 $ ; - if $ l = 3 $ and $ r = 5 $ we will have a permutation $ [1, 3, 2] $ for $ m = 3 $ ; - if $ l = 1 $ and $ r = 5 $ we will have a permutation $ [4, 5, 1, 3, 2] $ for $ m = 5 $ ; - if $ l = 1 $ and $ r = 6 $ we will have a permutation $ [4, 5, 1, 3, 2, 6] $ for $ m = 6 $ ; - it is impossible to take some $ l $ and $ r $ , such that $ [p_l, p_{l+1}, \ldots, p_r] $ is a permutation of numbers $ 1, 2, \ldots, m $ for $ m = 2 $ and for $ m = 4 $ . You are given a permutation $ p=[p_1, p_2, \ldots, p_n] $ . For all $ m $ ( $ 1 \le m \le n $ ) determine if it is a beautiful number or not.

输入输出格式

输入格式

The first line contains the only integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases in the input. The next lines contain the description of test cases. The first line of a test case contains a number $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the given permutation $ p $ . The next line contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ , all $ p_i $ are different) — the given permutation $ p $ . It is guaranteed, that the sum of $ n $ from all test cases in the input doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

Print $ t $ lines — the answers to test cases in the order they are given in the input. The answer to a test case is the string of length $ n $ , there the $ i $ -th character is equal to $ 1 $ if $ i $ is a beautiful number and is equal to $ 0 $ if $ i $ is not a beautiful number.

输入输出样例

输入样例 #1

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

输出样例 #1

101011
11111
1001

说明

The first test case is described in the problem statement. In the second test case all numbers from $ 1 $ to $ 5 $ are beautiful: - if $ l = 3 $ and $ r = 3 $ we will have a permutation $ [1] $ for $ m = 1 $ ; - if $ l = 3 $ and $ r = 4 $ we will have a permutation $ [1, 2] $ for $ m = 2 $ ; - if $ l = 2 $ and $ r = 4 $ we will have a permutation $ [3, 1, 2] $ for $ m = 3 $ ; - if $ l = 2 $ and $ r = 5 $ we will have a permutation $ [3, 1, 2, 4] $ for $ m = 4 $ ; - if $ l = 1 $ and $ r = 5 $ we will have a permutation $ [5, 3, 1, 2, 4] $ for $ m = 5 $ .