Для бинарной строки$$$^{\text{∗}}$$$ $$$v$$$ определим счёт $$$v$$$ как максимальное значение
$$$$$$F\big(v, 1, i\big) \cdot F\big(v, i+1, |v|\big)$$$$$$
по всем $$$i$$$ ($$$0 \leq i \leq |v|$$$).
Здесь $$$F\big(v, l, r\big) = r - l + 1 - 2 \cdot \operatorname{zero}(v, l, r)$$$, где $$$\operatorname{zero}(v, l, r)$$$ обозначает количество $$$\mathtt{0}$$$ в $$$v_lv_{l+1} \ldots v_r$$$. Если $$$l \gt r$$$, то $$$F\big(v, l, r\big) = 0$$$.
Вам дана бинарная строка $$$s$$$ длины $$$n$$$ и целое положительное число $$$q$$$.
Вам будет задано $$$q$$$ запросов.
В каждом запросе вам дано целое число $$$i$$$ ($$$1 \leq i \leq n$$$). Вы должны изменить $$$s_i$$$ с $$$\mathtt{0}$$$ на $$$\mathtt{1}$$$ (или с $$$\mathtt{1}$$$ на $$$\mathtt{0}$$$). Найдите сумму счётов по всем непустым подпоследовательностям$$$^{\text{†}}$$$ $$$s$$$ после каждого запроса на изменение.
Поскольку ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.
Обратите внимание, что изменения являются постоянными.
$$$^{\text{∗}}$$$Бинарная строка — это строка, состоящая только из символов $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$.
$$$^{\text{†}}$$$Бинарная строка $$$x$$$ является подпоследовательностью бинарной строки $$$y$$$, если $$$x$$$ может быть получена из $$$y$$$ путем удаления нескольких (возможно, нуля или всех) символов.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$) — длина строки $$$s$$$ и количество запросов на изменение соответственно.
Вторая строка содержит бинарную строку $$$s$$$ длины $$$n$$$, состоящую из символов $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$.
Каждая из следующих $$$q$$$ строк содержит целое число $$$i$$$ ($$$1 \leq i \leq n$$$), указывающее, что $$$s_i$$$ изменяется с $$$\mathtt{0}$$$ на $$$\mathtt{1}$$$ или с $$$\mathtt{1}$$$ на $$$\mathtt{0}$$$.
Гарантируется, что сумма $$$n$$$ и сумма $$$q$$$ по всем наборам входных данных не превосходят $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$q$$$ строк, каждая из которых содержит одно целое число — требуемую сумму по модулю $$$998\,244\,353$$$.
33 20101310 30101000110351024 101100110011000010111100024
1 5 512 768 1536 23068672
Для первого набора входных данных, после первого изменения имеем $$$s = \texttt{110}$$$. Мы можем вычислить сумму счётов по всем подпоследовательностям следующим образом:
| Индексы | Подпоследовательность | Счёт |
| $$$1$$$ | 1 | $$$0$$$ |
| $$$2$$$ | 1 | $$$0$$$ |
| $$$1, 2$$$ | 11 | $$$1$$$ |
| $$$3$$$ | 0 | $$$0$$$ |
| $$$1, 3$$$ | 10 | $$$0$$$ |
| $$$2, 3$$$ | 10 | $$$0$$$ |
| $$$1, 2, 3$$$ | 110 | $$$0$$$ |
Суммируя: $$$0+0+1+0+0+0+0 = 1$$$.
После второго изменения, имеем $$$s = \texttt{111}$$$. Мы можем вычислить сумму счётов по всем подпоследовательностям следующим образом:
| Индексы | Подпоследовательность | Счёт |
| $$$1$$$ | 1 | $$$0$$$ |
| $$$2$$$ | 1 | $$$0$$$ |
| $$$1, 2$$$ | 11 | $$$1$$$ |
| $$$3$$$ | 1 | $$$0$$$ |
| $$$1, 3$$$ | 11 | $$$1$$$ |
| $$$2, 3$$$ | 11 | $$$1$$$ |
| $$$1, 2, 3$$$ | 111 | $$$2$$$ |
Суммируя: $$$0+0+1+0+1+1+2 = 5$$$.
| Codeforces Round 1008 (Div. 1) |
|---|
| Закончено |
