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 all subsequences — $$$S$$$ and the number of all 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,

The same principle applies for the rest of the types.

Secondly, we will combine sum of subsequences of each type.

There are two cases:

Hence, the sum of $$$f(b)$$$ over all $$$0 \dots 0$$$ is:

The contribution of each subsequence from the $$$L$$$ is $$$S_{L} \cdot C_{R}$$$ and vice versa. Note that we $$$\color{red}{\text{subtract}}$$$ contribution of all subsequences $$$C_{L} \cdot C_{R}$$$ in case edge-elements are equal.

The same principle also applies for the rest of the types.

4. Code

Finally, to solve the problem we will use a Segment Tree in which we will store the above listed values. To make writing code easier, there are some advice:

1. Use struct node with all mentioned variables.
2. Write function combine(v, l, r) which will combine left node and right node.
3. To handle range queries, just write get() function and combine all visited vertex like in a build() function of Segment Tree.
4. (?) Maybe it is possible to reduce the amount of code with bitmasks, but i am not sure about the constant factor.

So, the total complexity is $$$O(n)$$$ memory and $$$O(n + q \log n)$$$ time.

Here you can check my code: https://codeforces.net/contest/2065/submission/305351558

Hope this was interesting enough.