Narrow Components
Contest: Educational Codeforces Round 126 (Rated for Div. 2)
Difficulty rating: 2500
Tags: brute force, data structures, dp, dsu, math, trees

You are given a matrix $$$a$$$, consisting of $$$3$$$ rows and $$$n$$$ columns. Each cell of the matrix is either free or taken.

A free cell $$$y$$$ is reachable from a free cell $$$x$$$ if at least one of these conditions hold:

- $$$x$$$ and $$$y$$$ share a side;
- there exists a free cell $$$z$$$ such that $$$z$$$ is reachable from $$$x$$$ and $$$y$$$ is reachable from $$$z$$$.

A connected component is a set of free cells of the matrix such that all cells in it are reachable from one another, but adding any other free cell to the set violates this rule.

You are asked $$$q$$$ queries about the matrix. Each query is the following:

- $$$l$$$ $$$r$$$ — count the number of connected components of the matrix, consisting of columns from $$$l$$$ to $$$r$$$ of the matrix $$$a$$$, inclusive.

Print the answers to all queries.

Input format:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of columns of matrix $$$a$$$.

The $$$i$$$-th of the next three lines contains a description of the $$$i$$$-th row of the matrix $$$a$$$ — a string, consisting of $$$n$$$ characters. Each character is either $$$1$$$ (denoting a free cell) or $$$0$$$ (denoting a taken cell).

The next line contains an integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

The $$$j$$$-th of the next $$$q$$$ lines contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — the description of the $$$j$$$-th query.

Output format:
Print $$$q$$$ integers — the $$$j$$$-th value should be equal to the number of the connected components of the matrix, consisting of columns from $$$l_j$$$ to $$$r_j$$$ of the matrix $$$a$$$, inclusive.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
12
100101011101
110110010110
010001011101
8
1 12
1 1
1 2
9 9
8 11
9 12
11 12
4 6

Example output:
7
1
1
2
1
3
3
3

Editorial:
Consider the naive approach to the problem.
Cut off the columns directly and count the connected components. There are two main solutions to this problem: either DFS (or BFS) or DSU. I personally found the DSU method easier to adjust to the full problem.
So, to count connected components with DSU, you should do the following. Initialize the structure without edges: every free cell is its own connected component. Then add edges one by one. Each edge connects two cells either vertically or horizontally. When an edge connects different components, they merge, and the number of components decreases by one.
Thus, the number of components on a range of columns is the number of free cells on it minus the number of meaningful edges on it (the ones that will merge components if the algorithm is performed only on these columns — the spanning forest edges).
Let's try to adjust this algorithm to the full problem. It would be great if we could just calculate the spanning forest of the entire matrix, and then print the number of free cells minus the number of its edges on the segment. Unfortunately, it's not as easy as that. For components that lie fully in the segment, it works. However, if a component is split by a border of a segment, it can both stay connected or fall apart. If we determine its outcome, we can fix the answer.
There are probably a lot of ways to adjust for that, but I'll tell you the one I found the neatest to code. Let's add the edges into DSU in the following order. Go column by column left to right. First add all vertical edges in any order, then all horizontal edges to the previous column in any order.
If you start this algorithm at the first column, you will be able to answer all queries with $$$l=1$$$. Since the algorithm adds columns iteratively, the spanning forest it's building is correct after every column. So the answer for each query is indeed the number of cells minus the number of edges on the range.
Let's investigate the difference between starting at the first column and an arbitrary column $$$l$$$.
Look at the column $$$l$$$. If it contains $$$1$$$ or $$$3$$$ free cells or $$$2$$$ that are adjacent, then the cells are always in the same component, regardless of what has been before column $$$l$$$. If there are no free cells, nothing to the left matters, too. This tells us that the spanning forest that the first algorithm has built, is correct for any queries that start in this $$$l$$$.
The only non-trivial case is when only rows $$$1$$$ and $$$3$$$ of the $$$l$$$-th column contain a free cell. Then we can't tell if the algorithm is correct or not, because these two cells can be in the same component already or not. Let's call this a "101" column.
Imagine you started processing from the leftmost column of the query, left to right to the rightmost column. Our previous observations tell us that once we encounter a column that is not a "101", the algorithm onwards will be correct. Until then, we only have some "101" columns to deal with.
We can add the part from the first non-"101" column onwards to the answer (the number of cells minus the number of edges). And then handle the prefix with some easy casework:
• if the leftmost column is not "101", then add nothing;
• if all columns in the query are "101", then the answer is $$$2$$$;
• if the first non-"101" column is "111", then add nothing (since the "101"s get merged into the component of this column);
• if the first non-"101" column is "000" or "010", then add $$$2$$$ components (since neither row $$$1$$$ nor row $$$3$$$ is merged anywhere);
• otherwise, add $$$1$$$ component.
The number of free cells and edges on a segment can be precalculated with some prefix sums. The closest non-"101" column can also be precalculated with a linear algorithm.
Overall complexity: $$$O(n \cdot \alpha(n) + q)$$$.