CF1450D Rating Compression

在竞赛编程平台 CodeCook 上，每个人都有一个由长度为 $n$ 的整数数组 $a$ 描述的评分曲线。你现在正在升级基础设施，因此你编写了一个程序来压缩这些曲线。 程序的工作方式如下。给定一个整数参数 $k$，程序会取出 $a$ 中每个长度为 $k$ 的连续子数组的最小值。 更正式地说，对于长度为 $n$ 的数组 $a$ 和整数 $k$，定义 $a$ 的 $k$ 压缩数组为长度为 $n-k+1$ 的数组 $b$，其中 $$ b_j =\min_{j\le i\le j+k-1}a_i $$ 例如，$[1, 3, 4, 5, 2]$ 的 $3$ 压缩数组为 $[\min\{1, 3, 4\}, \min\{3, 4, 5\}, \min\{4, 5, 2\}] = [1, 3, 2]$。 长度为 $m$ 的排列是指由 $1$ 到 $m$ 的 $m$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$m=3$ 但数组中有 $4$）。 如果 $k$ 压缩数组是一个排列，则会让 CodeCook 用户感到高兴。给定数组 $a$，请判断对于所有 $1\leq k\leq n$，经过 $k$ 压缩后 CodeCook 用户是否会高兴。

第一行包含一个整数 $t$（$1\leq t\leq 10^4$）——表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1\leq n\leq 3\cdot 10^5$）——数组的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1,\ldots,a_n$（$1\leq a_i\leq n$）——数组的元素。 保证所有测试用例中 $n$ 的总和不超过 $3\cdot 10^5$。

对于每个测试用例，输出一个长度为 $n$ 的二进制字符串。 第 $k$ 个字符应为 $1$，如果数组 $a$ 的 $k$ 压缩后 CodeCook 用户会高兴，否则为 $0$。

在第一个测试用例中，$a=[1, 5, 3, 4, 2]$。 - $1$ 压缩后为 $[1, 5, 3, 4, 2]$，是一个排列。 - $2$ 压缩后为 $[1, 3, 3, 2]$，不是排列，因为 $3$ 出现了两次。 - $3$ 压缩后为 $[1, 3, 2]$，是一个排列。 - $4$ 压缩后为 $[1, 2]$，是一个排列。 - $5$ 压缩后为 $[1]$，是一个排列。 由 ChatGPT 4.1 翻译