CF2259F.Binary Bubble Sort Inversions

Define performing a bubble on an array $b_1, b_2, \ldots, b_m$ to be performing the following action:

• For each integer $i$ ($1 \leq i \lt m$) in order, if $b_i \gt b_{i+1}$, swap $b_i$ and $b_{i+1}$.

Define performing a reverse bubble on an array $b_1, b_2, \ldots, b_m$ to be performing the following action:

• For each integer $i$ ($1 \leq i \lt m$) in reverse order, if $b_i \gt b_{i+1}$, swap $b_i$ and $b_{i+1}$.

For example, if we perform a bubble on $[1, 1, 0]$, we would transform it as follows: $[\color{red}{1, 1}, 0] \to [1, \color{red}{1, 0}] \to [1, 0, 1]$. If we perform a reverse bubble on $[1, 1, 0]$, we would transform it as follows: $[1, \color{red}{1, 0}] \to[\color{red}{1, 0}, 1] \to [0, 1, 1]$.

You are given an array $a_1, a_2, \ldots, a_n$ consisting of only 0s and 1s and a binary string$^{\text{∗}}$ $s$ of length $n$. You perform $n$ operations in order, where the $i$-th operation performs a bubble on $a$ if $s_i = \texttt{1}$ and performs a reverse bubble on $a$ if $s_i = \texttt{0}$. For each of the $n + 1$ states of $a$ — before any operations have been performed and after each operation — count the number of inversions$^{\text{†}}$ in $a$.

$^{\text{∗}}$A binary string is a string that only contains 0s and 1s.

$^{\text{†}}$An inversion in an array $c$ of length $m$ is a pair of indices $i, j$ such that $1 \leq i \lt j \leq m$ and $c_i \gt c_j$.

定义对数组 $b_1, b_2, \ldots, b_m$ 执行一次**冒泡操作（bubble）**为执行以下动作：

• 按顺序对每个整数 $i$（$1 \leq i \lt m$），若 $b_i \gt b_{i+1}$，则交换 $b_i$ 与 $b_{i+1}$。

定义对数组 $b_1, b_2, \ldots, b_m$ 执行一次**反向冒泡操作（reverse bubble）**为执行以下动作：

• 按逆序对每个整数 $i$（$1 \leq i \lt m$），若 $b_i \gt 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$ 的二进制字符串$^{\text{∗}}$ $s$。你将按顺序执行 $n$ 次操作：第 $i$ 次操作中，若 $s_i = \texttt{1}$，则对 $a$ 执行一次冒泡操作；若 $s_i = \texttt{0}$，则对 $a$ 执行一次反向冒泡操作。对于 $a$ 的 $n + 1$ 个状态——即初始状态（尚未执行任何操作）以及每次操作之后的状态——请分别统计此时 $a$ 中的逆序对数$^{\text{†}}$。

$^{\text{∗}}$二进制字符串是指仅包含字符 0 和 1 的字符串。

$^{\text{†}}$数组 $c$（长度为 $m$）中的一个逆序对是指一对下标 $(i, j)$，满足 $1 \leq i \lt j \leq m$ 且 $c_i \gt c_j$。

The first line of each input contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains $n$ ($1 \leq n \leq 5 \cdot 10^5$) — the length of $a$ and $s$.

The second line of each test case contains $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 1$) — the array $a$.

The third line of each test case contains $s$ ($s_i \in {0, 1}$, $|s| = n$$^{\text{∗}}$) — the binary string $s$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

$^{\text{∗}}$$|c|$ denotes the length of a string $c$.

每组输入的第一行包含 $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$。

每个测试用例的第三行包含字符串 $s$（$s_i \in \{0, 1\}$，$|s| = n$$^{\text{∗}}$）—— 二进制字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

$^{\text{∗}}$$|c|$ 表示字符串 $c$ 的长度。

For each test case, output $n + 1$ space separated integers, the $i$-th integer denoting the number of inversions in $a$ after the first $i - 1$ operations have been performed.

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

In the first test case:

• Before any operations: $a = [1, 1, 0, 0]$, which has $4$ inversions.
• After the first operation: $a = [1, 0, 0, 1]$, which has $2$ inversions.
• After the second operation: $a = [0, 1, 0, 1]$, which has $1$ inversion.
• After the third operation: $a = [0, 0, 1, 1]$, which has $0$ inversions.
• After the fourth operation: $a = [0, 0, 1, 1]$, which has $0$ inversions.

在第一个测试用例中：

• 任何操作之前：$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$。