Build From Suffixes
Contest: Kotlin Heroes: Episode 6
Difficulty rating: 2800
Tags: *special, combinatorics, data structures

You are given an integer $$$n$$$ and a sequence $$$a$$$ of $$$n-1$$$ integers, each element is either $$$0$$$ or $$$1$$$.

You are asked to build a string of length $$$n$$$ such that:

- each letter is one of "abcd";
- if $$$a_i=1$$$, then the $$$i$$$-th suffix of the string is lexicographically smaller than the $$$(i+1)$$$-th suffix;
- if $$$a_i=0$$$, then the $$$i$$$-th suffix of the string is lexicographically greater than the $$$(i+1)$$$-th suffix.

You will be asked $$$q$$$ queries of form:

- $$$i$$$ ($$$1 \le i \le n - 1$$$) — flip the value of $$$a_i$$$ (if $$$a_i=0$$$, then set $$$a_i$$$ to $$$1$$$, and vice versa).

After each query print the number of different strings that satisfy the given constraints modulo $$$998\,244\,353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 10^5$$$; $$$1 \le q \le 10^5$$$) — the length of the string and the number of queries.

The second line contains $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$a_i \in \{0, 1\}$$$) — the constraints on suffixes of the string.

Each of the next $$$q$$$ lines contains a query: an integer $$$i$$$ ($$$1 \le i \le n - 1$$$) — flip the value of $$$a_i$$$ (if $$$a_i=0$$$, then set $$$a_i$$$ to $$$1$$$, and vice versa).

Output format:
After each query print the number of different strings that satisfy the given constraints modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 10.0 s
Memory limit: 512.0 MB

Note:
The $$$i$$$-th suffix of a string is a continuous substring that starts from the $$$i$$$-th position and ends in the last position.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Two strings $$$a$$$ and $$$b$$$ of length $$$n$$$ differ if there exists a position $$$i$$$ such that $$$a_i \neq b_i$$$.

Example input:
2 2
0
1
1

Example output:
6
10

Example input:
3 4
0 0
1
2
1
2

Example output:
20
10
14
20

Editorial:
Let's simplify the problem and at least solve it without the updates.
Take a look at some string $$$s$$$ of length $$$n$$$. What does the comparison of some suffixes $$$i$$$ and $$$i+1$$$ actually imply? If $$$s_i \neq s_{i+1}$$$, then you can immediately say the result of the comparison. Otherwise, you can remove the first letter from both these suffixes and the result of comparison doesn't change. However, both suffixes with the first letter removed are actually suffixes $$$i+1$$$ and $$$i+2$$$. Thus, the result of comparison should be the same.
You can also append $$$a$$$ with $$$0$$$ to get rid of corner cases. The last suffix is always greater than the empty one.
Now the first thing that comes to mind is some dynamic programming that builds the string from the end and keeps track of the last letter. So let $$$dp[i][c]$$$ be the number of strings such that the $$$i$$$-th suffix is set, all the conditions from the $$$i$$$-th to the $$$n$$$-th are satisfied and the last (the $$$i$$$-th) letter is $$$c$$$. We can iterate on the value of the $$$(i-1)$$$-th letter and put it according to the value of $$$a_{i-1}$$$ and $$$a_i$$$. So far, we have to iterate on both the current and the previous letter to make a transition. However, you can notice that each transition sums up the values of dp from all letters either greater than the current one or smaller than the current one. With some small prefix sum magic we can do that dp in $$$O(nk)$$$.
Point updates tell us that the problem can include some data structure. For example, let's try to put that dp inside the segment tree. What information do we have to maintain in dp to be able to merge two segments together? Similar to the case without the updates, we don't really care about the full insides of the string. However, since we can merge from both left and right now, we should store the leftmost and the rightmost letters. Each node can store $$$dp[c_l][c_r]$$$ — the number of valid strings on the corresponding segment such that their leftmost letter is $$$c_l$$$ and their rightmost letter is $$$c_r$$$.
To merge two segments we can iterate over the rightmost letter of the left segment and the leftmost letter of the right segment and multiply the values of their dp if the conditions of $$$a$$$ hold. We also have to iterate on the leftmost letter of the left segment and the rightmost letter of the right segment, thus, the merge works in $$$4^4$$$ so far. Similar to the $$$O(nk)$$$ solution, you can use prefix sums to get rid of one multiplier of $$$4$$$.
Overall complexity: $$$O((n + q) \cdot \log n \cdot |A|^3)$$$, where $$$|A|=4$$$.