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 \lt |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:
- Subsequence starts with "0" and ends with "0" — $$$0\dots0$$$
- Subsequence starts with "0" and ends with "1" — $$$0\dots1$$$
- Subsequence starts with "1" and ends with "0" — $$$1\dots0$$$
- Subsequence starts with "1" and ends with "1" — $$$1\dots1$$$
Let's store $$$2$$$ variables for each type of the 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:
- $$$\color{red}{0} \dots0$$$ and $$$0\dots \color{blue}{0}$$$
- $$$\color{red}{0} \dots0$$$ and $$$1\dots \color{blue}{0}$$$
- $$$\color{red}{0} \dots1$$$ and $$$0\dots \color{blue}{0}$$$
- $$$\color{red}{0} \dots1$$$ and $$$1\dots \color{blue}{0}$$$
Hence,
The same principle applies for the rest of the types ($$$0 \dots 1$$$, $$$1 \dots 0$$$, $$$1 \dots 1$$$).
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 (we subtract $$$1$$$ in all these cases).
The same principle also applies for the rest of the types ($$$0 \dots 1$$$, $$$1 \dots 0$$$, $$$1 \dots 1$$$).
When we have combined two parts, answer is $$$S(0 \dots 0) + S(0 \dots 1) + S(1 \dots 0) + S(1 \dots 1)$$$. Do not forget to use modular arithmetic.
4. Code
Finally, to solve the problem we will use a Segment Tree in which the above listed values will be stored. To make writing code easier, there are some advice:
- Use
struct nodeorarray<int, 8>with all mentioned variables. - Write function
combine(v, l, r)which will combine left node and right node. - To handle range queries, just write
get()function and combine all visited vertex like in abuild()function of Segment Tree. - (?) 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.me/contest/2065/submission/305351558
Hope this was interesting enough.
