CF2163B Siga ta Kymata

给定一个长度为 $n$ 的排列 $p$，它包含了 $1$ 到 $n$ 每个整数各一次。同时，给定一个长度为 $n$ 的二进制字符串 $s$，其中 $s_i = 0$，对所有 $1 \le i \le n$ 都成立。你可以最多进行 $5$ 次如下操作： - 选择任意两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le n$。对于所有满足 $l < i < r$ 且 $\min(p_l, p_r) < p_i < \max(p_l, p_r)$ 条件的 $i$，将 $s_i$ 置为 $1$。 你还给定了一个长度为 $n$ 的二进制字符串 $x$。在操作结束后，要求对于每一个 $1 \le i \le n$，如果 $x_i = 1$，则 $s_i$ 必须等于 $1$。注意，如果 $x_i = 0$，那么 $s_i$ 可以为任意值。 请找出至多 $5$ 次操作的任意一个方案，使上述条件被满足。如果无法做到，输出不可能。你不需要让操作次数最少。 $^\text{∗}$排列 $p$ 是指由 $1$ 到 $n$ 组成的序列，每个元素各出现一次。 $^\text{†}$二进制字符串 $b$ 的定义是：对于所有 $1 \le i \le m$，$b_i$ 只能是字符 $0$ 或 $1$。

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例组数。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）——排列的大小。 第二行包含恰好 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$，每个数字各出现一次），表示排列 $p$。 第三行包含一个长度为 $n$ 的二进制字符串 $x$。 保证所有测试用例中 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果无法通过操作满足条件，输出 $-1$。 否则，输出一个整数 $0 \le k \le 5$，表示操作次数。接下来的 $k$ 行，每行输出两个整数 $1 \le l_i \le r_i \le n$，表示第 $i$ 次操作的区间。如果有多种方案，输出任意一种均可。

在第一个样例中，$p = [1, 2, 3]$，$x = 010$。我们可以只进行一次操作，选择 $l = 1$，$r = 3$。操作后，因为 $l < 2 < r$ 且 $\min(p_l, p_r) < p_2 = 2 < \max(p_l, p_r)$ 成立，将 $s_2$ 置为 $1$，最终 $s = 010$。 在第二个样例中，可以证明不存在不超过 $5$ 次操作能满足条件，因此输出 $-1$。 在第三个样例中，$p = [1, 3, 2, 4, 6, 5]$，$x = 001100$。先对 $l = 1$ 和 $r = 5$ 操作，此时 $s = 011100$。再对 $l = 2$ 和 $r = 6$ 操作，$s$ 保持不变。最终 $s = 011100$ 满足条件，因为 $x$ 中每个为 $1$ 的位置，$s$ 对应位置也为 $1$。 由 ChatGPT 5 翻译