AT_agc076_b.[AGC076B] Split and Reverse

给定一个长度为 $N$ 的整数序列 $X = (X_1, X_2, \cdots, X_N)$，其中每个元素均为 $0$ 或 $1$。

你可以执行以下操作任意次（包括零次）：

• 将 $X$ 的每个元素划分到组 A 或组 B。对每一组，将其包含的元素整体翻转顺序。更正式地说，若某组包含的元素为 $X_{i_1}, X_{i_2}, \cdots, X_{i_s}$（$i_1 < i_2 < \cdots < i_s$），则对所有 $1 \leq j \leq s$，同时将 $X_{i_j}$ 替换为 $X_{i_{s+1-j}}$。

你的目标是将 $X$ 变为非递减序列。请找出达到该目标所需的最少操作次数以及具体的操作方式。在本题的限制下，可以保证一定存在解。

对于一组输入，请解决 $T$ 个测试用例。

输入通过标准输入给出，格式如下：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每个测试用例如下格式：

$N$ $X_1$ $X_2$ $\cdots$ $X_N$

对于每个测试用例，输出如下格式：

$k$ $s_1$ $s_2$ $\vdots$ $s_k$

其中，$k$ 表示所需的最少操作次数，$s_i$ 是表示第 $i$ 次操作的字符串。$s_i$ 是由 A 和 B 组成的长度为 $N$ 的字符串，第 $j$ 个字符表示本次操作中 $X_j$ 分到哪个组。如果有多组解，输出任意一种都可以。

样例解释 1

对于第一个测试用例，可以通过如下两步达到目标，这也是最少的操作次数：

• 第一步操作：使用 $s_1=$AABA。由于 $(X_1, X_2, X_4)$ 被分入组 A，翻转其顺序后得到 $(X_1, X_2, X_4) = (1, 1, 0)$。而 $(X_3)$ 被分入组 B，翻转后还是 $(0)$。因此总体得到 $X = (1, 1, 0, 0)$。
• 第二步操作：使用 $s_2=$BBBB。此时组 A 为空，翻转无影响。$(X_1, X_2, X_3, X_4)$ 全部分到组 B，翻转后序列变为 $(0, 0, 1, 1)$，因此 $X = (0, 0, 1, 1)$。

对于第二个测试用例，可以不进行任何操作。

约束条件

• $1 \leq T \leq 250000$
• $1 \leq N \leq 250000$
• $0 \leq X_i \leq 1$
• 所有 $T$ 个测试用例的 $N$ 之和不超过 $250000$。
• 所有输入值均为整数。

由 ChatGPT 5 翻译