Hello Сodeforces,

Recently the Div. 4 round was held with quite balanced and beautiful problems. I especially liked Problem H, where I accidentally overkilled the solution. I want to share with you a solution I came up with that supports range queries in $$$O(n + q \log n)$$$.

1. Some observations

Firstly, one should notice that value of $$$f(b)$$$ equals to ( number of $$$i$$$ : $$$b_{i} \neq b_{i+1}$$$ for $$$(1 \leq i < |b|)$$$ ) $$$+$$$ $$$1$$$. For binary strings, that means $$$f(b) = (\text{number of "10"}) + (\text{number of "01"}) + 1$$$.

Secondly, when there are update-queries mentioned in the problem, one should consider using some data structures.

2. Main idea

Suppose we have two binary strings $$$L$$$ and $$$R$$$ and we know the answer for each of them. Now our goal is to figure out how we can combine them to get the answer for the full string.

All subsequences can be represented as follows:

1. Subsequence starts with "0" and ends with "0" — $$$0\dots0$$$
2. Subsequence starts with "0" and ends with "1" — $$$0\dots1$$$
3. Subsequence starts with "1" and ends with "0" — $$$1\dots0$$$
4. Subsequence starts with "1" and ends with "1" — $$$1\dots1$$$

Let's store $$$2$$$ variables for each type of subsequences: the sum of the $$$f(b)$$$ over subsequences — $$$S$$$ and the number of subsequences — $$$C$$$.

3. Combining parts

Firstly, we will combine number of subsequences of each type.

To get $$$\color{red}{0} \dots \color{blue}{0}$$$ we should combine:

1. $$$\color{red}{0} \dots0$$$ and $$$0\dots \color{blue}{0}$$$
2. $$$\color{red}{0} \dots0$$$ and $$$1\dots \color{blue}{0}$$$
3. $$$\color{red}{0} \dots1$$$ and $$$0\dots \color{blue}{0}$$$
4. $$$\color{red}{0} \dots1$$$ and $$$1\dots \color{blue}{0}$$$

Hence, $$$ C(0 \dots 0) = C_{L}(0 \dots 0) + C_{R}(0 \dots 0)$$$ $$$+$$$

$$$+$$$ $$$( C_{L}(\color{red}{0} \dots 0) \cdot C_{R}(0 \dots \color{blue}{0})) + ( C_{L}(\color{red}{0} \dots 0) \cdot C_{R}(1 \dots \color{blue}{0}))$$$ $$$+$$$

$$$+$$$ $$$( C_{L}(\color{red}{0} \dots 1) \cdot C_{R}(0 \dots \color{blue}{0})) + ( C_{L}(\color{red}{0} \dots 1) \cdot C_{R}(1 \dots \color{blue}{0}))$$$.