Narrow Components solution codeforces – You are given a matrix 𝑎a, consisting of 33 rows and 𝑛n columns. Each cell of the matrix is either free or taken.
[Solution] Narrow Components solution codeforces
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.
[Solution] Narrow Components solution codeforces
The first line contains an integer 𝑛n (1≤𝑛≤5⋅1051≤n≤5⋅105) — 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 11 (denoting a free cell) or 00 (denoting a taken cell).
The next line contains an integer 𝑞q (1≤𝑞≤3⋅1051≤q≤3⋅105) — the number of queries.
The 𝑗j-th of the next 𝑞q lines contains two integers 𝑙𝑗lj and 𝑟𝑗rj (1≤𝑙𝑗≤𝑟𝑗≤𝑛1≤lj≤rj≤n) — the description of the 𝑗j-th query.
Print 𝑞q integers — the 𝑗j-th value should be equal to the number of the connected components of the matrix, consisting of columns from 𝑙𝑗lj to 𝑟𝑗rj of the matrix 𝑎a, inclusive.
12 100101011101 110110010110 010001011101 8 1 12 1 1 1 2 9 9 8 11 9 12 11 12 4 6
Narrow Components solution codeforces
7 1 1 2 1 3 3 3