AT_tupc2024_j.Median Operations

给定一个正的奇数 $N$，以及 $(1, 2, \ldots, N)$ 的一个排列 $P = (P_1, P_2, \ldots, P_N)$。

你最初拥有一个数列 $A = P$，你可以对数列 $A$ 重复进行如下操作：

• 选择 $A$ 的一个奇数长度的连续子序列。设选中的连续子序列的中位数为 $m$，从 $A$ 中删除该连续子序列，并在其位置插入 $m$。
  • 更加严格地说，选择满足 $1 \leq l \leq r \leq |A|$ 并且 $r-l+1$ 为奇数的整数对 $(l, r)$。令 $(A_l, A_{l+1}, \ldots, A_r)$ 的中位数为 $m$，将 $A$ 替换为 $(A_1, \ldots, A_{l-1}, m, A_{r+1}, \ldots, A_n)$。

对于每个 $k = 1, 2, \ldots, N$，请判断通过若干次操作后，能否将 $A$ 变为长度为 $1$ 的数列 $(k)$。

有 $T$ 个测试用例，请分别回答。

输入通过标准输入按以下格式给出：

$T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$

其中 $\text{case}_i$ 表示第 $i$ 个测试用例，每个测试用例的格式如下：

$N$ $P_1$ $P_2$ $\ldots$ $P_N$

请输出 $T$ 行。

第 $i$ 行输出第 $i$ 个测试用例的答案，为长度为 $N$ 的字符串。第 $k$ 位为 1 表示可以通过若干次操作将序列变为 $(k)$，否则为 0。

部分分数

• 对于满足额外约束“每个输入文件中所有 $N$ 的总和不超过 $5000$”的数据集，答对可获得 $10$ 分。

样例解释 1

对于第 $1$ 个测试用例：

• 当 $k=3$ 时：选择 $(l, r) = (1, 5)$，可以得到 $A = (3)$。
• 当 $k=4$ 时：先选择 $(l, r) = (1, 3)$，得到 $A = (2, 5, 4)$，再选择 $(l, r) = (1, 3)$，得到 $A = (4)$。
• 对于 $k=1,2,5$，不存在这样的操作序列。

数据范围

• $1 \leq T \leq 10^4$
• $3 \leq N \leq 2 \times 10^5$
• $N$ 为奇数
• $(P_1, P_2, \ldots, P_N)$ 是 $(1, 2, \ldots, N)$ 的一个排列
• 每个输入文件中所有 $N$ 的总和不超过 $2 \times 10^5$
• 所有输入均为整数

由 ChatGPT 5 翻译