F. Инверсии бинарной пузырьковой сортировки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим выполнение пузырька на массиве $$$b_1, b_2, \ldots, b_m$$$ как выполнение следующего действия:

  • Для каждого целого $$$i$$$ ($$$1 \leq i \lt m$$$) по порядку, если $$$b_i \gt b_{i+1}$$$, поменять местами $$$b_i$$$ и $$$b_{i+1}$$$.
Определим выполнение обратного пузырька на массиве $$$b_1, b_2, \ldots, b_m$$$ как выполнение следующего действия:
  • Для каждого целого $$$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]$$$.

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$, состоящий только из 0 и 1, и бинарная строка$$$^{\text{∗}}$$$ $$$s$$$ длины $$$n$$$. Вы выполняете $$$n$$$ операций по порядку, где $$$i$$$-я операция выполняет пузырёк на $$$a$$$, если $$$s_i = \texttt{1}$$$, и выполняет обратный пузырёк на $$$a$$$, если $$$s_i = \texttt{0}$$$. Для каждого из $$$n + 1$$$ состояний $$$a$$$ — до выполнения каких-либо операций и после каждой операции — посчитайте количество инверсий$$$^{\text{†}}$$$ в $$$a$$$.

$$$^{\text{∗}}$$$Бинарная строка — это строка, которая содержит только символы 0 и 1.

$$$^{\text{†}}$$$Инверсией в массиве $$$c$$$ длины $$$m$$$ называется пара индексов $$$i, j$$$ такая, что $$$1 \leq i \lt j \leq m$$$ и $$$c_i \gt c_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$$$.

Третья строка каждого набора входных данных содержит $$$s$$$ ($$$s_i \in \{0, 1\}$$$, $$$|s| = n$$$$$$^{\text{∗}}$$$) — бинарную строку $$$s$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5 \cdot 10^5$$$.

$$$^{\text{∗}}$$$$$$|c|$$$ обозначает длину строки $$$c$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n + 1$$$ целых чисел, разделённых пробелами; $$$i$$$-е число обозначает количество инверсий в $$$a$$$ после выполнения первых $$$i - 1$$$ операций.

Пример
Входные данные
7
4
1 1 0 0
1010
7
0 1 0 1 1 0 0
0101001
4
0 0 1 1
1001
1
1
1
5
0 1 1 0 0
11101
3
1 0 0
000
6
1 0 1 1 0 0
011000
Выходные данные
4 2 1 0 0 
7 4 2 0 0 0 0 0 
0 0 0 0 0 
0 0 
4 2 0 0 0 0 
2 1 0 0 
7 4 2 1 0 0 0
Примечание

В первом наборе входных данных:

  • До выполнения каких-либо операций: $$$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$$$ инверсий.