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 翻译