P11282 「GFOI Round 2」Colors

> 世界が鮮やかに 染まって

有 $n$ 个球排成一排，从左到右依次编号为 $1 \sim n$。每个球初始都是红色的。第 $i$ 个球的初始权值为 $p_i$。**保证 $\bm{n}$ 为奇数且 $\bm{p}$ 是一个 $\bm{1 \sim n}$ 的排列。** 你需要恰好进行 $\frac{n - 1}{2}$ 次操作。在一次操作中，你需要： - 选择一个**红色**的球 $i$，使得 $1 \sim i - 1$ 中至少有一个红球且 $i + 1 \sim n$ 中至少有一个红球。 - 设 $j$ 为最大的整数使得 $j < i$ 且球 $j$ 为红球，$k$ 为最小的整数使得 $k > i$ 且球 $k$ 为红球。你要将球 $i$ 和球 $k$ 都染成蓝色。 - 然后进行以下两种操作的**恰好一个**： - 将 $p_j$（即球 $j$ 的权值）修改为 $\max(p_i, p_j, p_k)$； - 将 $p_j$（即球 $j$ 的权值）修改为 $\min(p_i, p_j, p_k)$。 容易发现进行了 $\frac{n - 1}{2}$ 次操作后恰好剩下一个红球。 你需要对于每个 $1 \sim n$ 的正整数 $x$，求出是否能合理地进行操作，使得最后剩下的红球的权值为 $x$。

**本题有多组测试数据。** 第一行包含一个正整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行包含一个正整数 $n$。 第二行包含 $n$ 个正整数 $p_1, p_2, \ldots, p_n$。

对于每组数据，输出一行一个 $01$ 串。对于每个 $1 \sim n$ 的正整数 $i$，若能合理地进行操作使得最后剩下的红球的权值为 $i$，那么这个 $01$ 串的第 $i$ 位为 $1$，否则为 $0$。

#### 【样例解释】 对于第一组数据，初始的球的状态（颜色和权值）依次为 $\color{red}{3\ 2\ 1}$。 你需要进行 $1$ 次操作。在这次操作中你只能选择球 $2$，将球 $2$ 和球 $3$ 染成蓝色。 - 若你选择将 $p_1$ 修改为 $\max(p_1, p_2, p_3)$，那么操作后球的状态变为 $\color{red}{3}\ \color{blue}{2\ 1}$，最后剩下的红球的权值为 $3$； - 若你选择将 $p_1$ 修改为 $\min(p_1, p_2, p_3)$，那么操作后球的状态变为 $\color{red}{1}\ \color{blue}{2\ 1}$，最后剩下的红球的权值为 $1$。 所以你输出一个 $01$ 串需要使得第 $1$ 和第 $3$ 位为 $1$，其余位为 $0$。 对于第二组数据，容易证明最后剩下的红球权值可以取 $1 \sim n$ 之间的所有正整数。下面给出一个能使得最后剩下的红球权值为 $2$ 的操作过程： - 初始的球的状态为 $\color{red}{1\ 3\ 5\ 2\ 4}$。 - 选择球 $2$，将球 $2$ 和球 $3$ 染成蓝色，并将 $p_1$ 赋值为 $\max(p_1, p_2, p_3) = 5$。操作后球的状态变为 $\color{red}{5}\ \color{blue}{3\ 5}\ \color{red}{2\ 4}$。 - 选择球 $4$，将球 $4$ 和球 $5$ 染成蓝色，并将 $p_1$ 赋值为 $\min(p_1, p_4, p_5) = 2$。操作后球的状态变为 $\color{red}{2}\ \color{blue}{3\ 5\ 2\ 4}$。 #### 【数据范围】 **本题采用捆绑测试。** | 子任务编号 | $n \le$ | $\sum n \le$ | 特殊性质 | 分值 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $5$ | $10^4$ | 无 | $16$ | | $2$ | $19$ | $10^4$ | 无 | $19$ | | $3$ | $99$ | $10^6$ | 无 | $19$ | | $4$ | $10^6 - 1$ | $10^6$ | A | $3$ | | $5$ | $10^6 - 1$ | $10^6$ | 无 | $43$ | - 特殊性质 A：$p_i = i$。 对于所有数据，满足： - $1 \le T \le 10^5$； - $3 \le n \le 10^6 - 1$ 且 $n$ 是奇数； - $\sum n \le 10^6$； - $p$ 是一个 $1 \sim n$ 的排列。