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 $ .

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 $ .

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.

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.