Background

Do not include mosaic.h when submitting.

Do not use C++14 (GCC 9) for submission.

Problem Description

Salma wants to color a clay mosaic on a wall. The mosaic consists of $N \times N$ square tiles, for a total of $N^2$ tiles. Each tile has size $1 \times 1$ and is initially uncolored. The rows of the mosaic are numbered from $0$ to $N-1$ from top to bottom, and the columns are numbered from $0$ to $N-1$ from left to right. The tile in row $i$ and column $j$ ($0 \leq i < N$, $0 \leq j < N$) is denoted $(i,j)$. Each tile is colored either white (denoted $0$) or black (denoted $1$).

To color the mosaic, Salma first chooses two arrays $X$ and $Y$ of length $N$, each consisting of $0$ and $1$, and with $X[0] = Y[0]$. She colors the top row (row $0$) according to array $X$, so that tile $(0,j)$ has color $X[j]$ ($0 \leq j < N$). She colors the leftmost column (column $0$) according to array $Y$, so that tile $(i,0)$ has color $Y[i]$ ($0 \leq i < N$).

Then she repeats the following steps until all tiles are colored:

• She finds any uncolored tile $(i,j)$ such that the tile directly above it $(i-1, j)$ and the tile directly to its left $(i, j-1)$ are both already colored.
• Then, if both of these adjacent tiles are white, she colors tile $(i,j)$ black; otherwise, she colors it white.

It can be proven that the final colors of the tiles do not depend on the order in which Salma colors them.

Yasmin is very curious about the colors of the mosaic tiles. She asks Salma $Q$ questions, numbered from $0$ to $Q-1$. In question $k$ ($0 \leq k < Q$), Yasmin specifies a rectangle in the mosaic using the following information:

• The top row $T[k]$ and the bottom row $B[k]$ ($0 \leq T[k] \leq B[k] < N$).
• The left column $L[k]$ and the right column $R[k]$ ($0 \leq L[k] \leq R[k] < N$).

The answer to a question is the number of black tiles inside that rectangle. More precisely, Salma should determine how many tiles $(i,j)$ satisfy $T[k] \leq i \leq B[k]$, $L[k] \leq j \leq R[k]$, and are colored black.

Write a program to answer Yasmin’s questions.

Implementation Details

You need to implement the following function.

std::vector<long long> mosaic(
	std::vector<int> X, std::vector<int> Y,
    std::vector<int> T, std::vector<int> B,
    std::vector<int> L, std::vector<int> R)

• $X$, $Y$: arrays of length $N$, describing the colors of the top row and the leftmost column, respectively.
• $T$, $B$, $L$, $R$: arrays of length $Q$, describing Yasmin’s questions.
• The function should return an array $C$ of length $Q$, where $C[k]$ gives the answer to question $k$ ($0 \leq k < Q$).
• For each test case, this function is called exactly once.

Input Format

The sample grader reads input in the following format:

N
X[0]  X[1]  ...  X[N-1]
Y[0]  Y[1]  ...  Y[N-1]
Q
T[0]  B[0]  L[0]  R[0]
T[1]  B[1]  L[1]  R[1]
...
T[Q-1]  B[Q-1]  L[Q-1]  R[Q-1]

Output Format

The sample grader prints your answers in the following format:

C[0]
C[1]
...
C[S-1]

Here, $S$ is the length of the array $C$ returned by mosaic.

4
1 0 1 0
1 1 0 1
2
0 3 0 3
2 3 0 2

7
3

Hint

Consider the following function call.

mosaic([1, 0, 1, 0], [1, 1, 0, 1], [0, 2], [3, 3], [0, 0], [3, 2])

This example is shown in the figure below. The figure on the left shows the colors of the tiles in the mosaic. The middle and right figures show the rectangles in Yasmin’s first and second questions, respectively.

The answers to the two questions (that is, the number of $1$ in the shaded rectangles) are $7$ and $3$, respectively. Therefore, the function should return $[7, 3]$.

Constraints

• $1 \leq N \leq 200\,000$
• $1 \leq Q \leq 200\,000$
• For all $i$ with $0 \leq i < N$, $X[i] \in \{0, 1\}$ and $Y[i] \in \{0, 1\}$.
• $X[0] = Y[0]$.
• For all $k$ with $0 \leq k < Q$, $0 \leq T[k] \leq B[k] < N$ and $0 \leq L[k] \leq R[k] < N$.

Translated by ChatGPT 5