Hello Сodeforces,↵
-----------------↵
↵
Recently the [Div. 4 round](https://codeforces.net/contest/2065) was held with quite balanced and beautiful problems. I especially liked [Problem H](https://codeforces.net/contest/2065/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 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:↵
↵
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}))$$↵
↵
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:↵
↵
$$↵
f(L+R) = ↵
\begin{cases}↵
f(L) + f(R) & \text{if last element of } L \neq \text{first element of } R \\↵
f(L) + f(R) - 1 & \text{if last element of } L = \text{first element of } R↵
\end{cases}↵
$$↵
↵
Hence, the sum of $f(b)$ over all $0 \dots 0$ is:↵
↵
$$S(0 \dots 0) = $$↵
↵
$$ = S_{L}(0 \dots 0) \cdot C_{R}(0 \dots 0) + C_{L}(0 \dots 0) \cdot S_{R}(0 \dots 0) - \color{red}{C_{L}(0 \dots 0) \cdot C_{R}(0 \dots 0)} +$$↵
↵
$$ + S_{L}(0 \dots 1) \cdot C_{R}(1 \dots 0) + C_{L}(0 \dots 1) \cdot S_{R}(1 \dots 0) - \color{red}{C_{L}(0 \dots 1) \cdot C_{R}(1 \dots 0)} + $$↵
↵
$$+ S_{L}(0 \dots 1) \cdot C_{R}(0 \dots 0) + C_{L}(0 \dots 1) \cdot S_{R}(0 \dots 0) + $$↵
↵
$$ + S_{L}(0 \dots 0) \cdot C_{R}(1 \dots 0) + C_{L}(0 \dots 0) \cdot S_{R}(1 \dots 0)$$↵
↵
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:↵
↵
1. Use `struct node` or `array<int, 8>` 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.
-----------------↵
↵
Recently the [Div. 4 round](https://codeforces.net/contest/2065) was held with quite balanced and beautiful problems. I especially liked [Problem H](https://codeforces.net/contest/2065/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 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:↵
↵
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}))$$↵
↵
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:↵
↵
$$↵
f(L+R) = ↵
\begin{cases}↵
f(L) + f(R) & \text{if last element of } L \neq \text{first element of } R \\↵
f(L) + f(R) - 1 & \text{if last element of } L = \text{first element of } R↵
\end{cases}↵
$$↵
↵
Hence, the sum of $f(b)$ over all $0 \dots 0$ is:↵
↵
$$S(0 \dots 0) = $$↵
↵
$$ = S_{L}(0 \dots 0) \cdot C_{R}(0 \dots 0) + C_{L}(0 \dots 0) \cdot S_{R}(0 \dots 0) - \color{red}{C_{L}(0 \dots 0) \cdot C_{R}(0 \dots 0)} +$$↵
↵
$$ + S_{L}(0 \dots 1) \cdot C_{R}(1 \dots 0) + C_{L}(0 \dots 1) \cdot S_{R}(1 \dots 0) - \color{red}{C_{L}(0 \dots 1) \cdot C_{R}(1 \dots 0)} + $$↵
↵
$$+ S_{L}(0 \dots 1) \cdot C_{R}(0 \dots 0) + C_{L}(0 \dots 1) \cdot S_{R}(0 \dots 0) + $$↵
↵
$$ + S_{L}(0 \dots 0) \cdot C_{R}(1 \dots 0) + C_{L}(0 \dots 0) \cdot S_{R}(1 \dots 0)$$↵
↵
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:↵
↵
1. Use `struct node` or `array<int, 8>` 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.
