[Solution] Narrow Components solution codeforces

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𝑛51051≤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𝑞31051≤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.

Output

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.

Example
input

Copy
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

output

Copy
7
1
1
2
1
3
3
3

 

For Solution

Click here

Leave a Comment