CF2259F Binary Bubble Sort Inversions

定义对数组 $b_1, b_2, \ldots, b_m$ 执行一次冒泡操作为如下动作： - 按顺序对于每个整数 $i$（$1 \leq i \lt m$），如果 $b_i > b_{i+1}$，则交换 $b_i$ 和 $b_{i+1}$。 定义对数组 $b_1, b_2, \ldots, b_m$ 执行一次反向冒泡操作为如下动作： - 按逆序对于每个整数 $i$（$1 \leq i \lt m$），如果 $b_i > b_{i+1}$，则交换 $b_i$ 和 $b_{i+1}$。 例如，如果我们对 $[1, 1, 0]$ 执行一次冒泡操作，变化过程如下： $[\color{red}{1, 1}, 0] \to [1, \color{red}{1, 0}] \to [1, 0, 1]$。如果对 $[1, 1, 0]$ 执行一次反向冒泡操作，变化过程如下：$[1, \color{red}{1, 0}] \to [\color{red}{1, 0}, 1] \to [0, 1, 1]$。 现在给定一个只由 $0$ 和 $1$ 组成的数组 $a_1, a_2, \ldots, a_n$，以及一个长度为 $n$ 的二进制字符串 $s$。你需要按顺序执行 $n$ 次操作，其中第 $i$ 次操作如果 $s_i = \texttt{1}$ 就对 $a$ 执行一次冒泡操作，如果 $s_i = \texttt{0}$ 就对 $a$ 执行一次反向冒泡操作。请在 $a$ 的 $n+1$ 个状态下（即尚未执行任何操作、以及每次操作之后），分别计算 $a$ 中的逆序对数。 *注：二进制字符串是指只由 $0$ 和 $1$ 组成的字符串。* *注：对于长度为 $m$ 的数组 $c$，其逆序对是指满足 $1 \leq i < j \leq m$ 且 $c_i > c_j$ 的一对索引 $(i, j)$。*

第一行包含 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$）——数组 $a$ 和字符串 $s$ 的长度。 每个测试用例的第二行为 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 1$）——数组 $a$。 每个测试用例的第三行包含一个长度为 $n$ 的二进制字符串 $s$（$s_i \in \{0, 1\}$，$|s| = n$）。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。 *注：$|c|$ 表示字符串 $c$ 的长度。*

对于每个测试用例，输出 $n+1$ 个用空格分隔的整数，第 $i$ 个整数表示在完成前 $i-1$ 次操作后的数组 $a$ 中逆序对的数量。

在第一个测试用例中： - 执行任何操作之前：$a = [1, 1, 0, 0]$，有 $4$ 对逆序对。 - 执行第一次操作后：$a = [1, 0, 0, 1]$，有 $2$ 对逆序对。 - 执行第二次操作后：$a = [0, 1, 0, 1]$，有 $1$ 对逆序对。 - 执行第三次操作后：$a = [0, 0, 1, 1]$，有 $0$ 对逆序对。 - 执行第四次操作后：$a = [0, 0, 1, 1]$，有 $0$ 对逆序对。 由 ChatGPT 5 翻译