题目背景

提交时请不要引用 mosaic.h。

请不要使用 C++14 (GCC 9) 提交。

题目描述

Salma 想给墙上的粘土马赛克上色。该马赛克由 $N \times N$ 片正方形瓷砖组成，共有 $N^2$ 片瓷砖；每片瓷砖的尺寸为 $1 \times 1$，都还没有上色。马赛克从上到下每行瓷砖的行编号从 $0$ 到 $N-1$，从左到右每列瓷砖的列编号从 $0$ 到 $N-1$。位于第 $i$ 行第 $j$ 列（$0 \leq i < N$，$0 \leq j < N$）的瓷砖记为 $(i,j)$。每片瓷砖要么涂成白色（记为 $0$），要么涂成黑色（记为 $1$）。

为了给马赛克上色，Salma 首先选取两个长度为 $N$ 的数组 $X$ 和 $Y$，每个数组都由 $0$ 和 $1$ 组成，并且 $X[0] = Y[0]$。她按照数组 $X$ 对最上面的行（第 $0$ 行）的瓷砖进行上色，使得瓷砖 $(0,j)$ 的颜色为 $X[j]$（$0 \leq j < N$）。她按照数组 $Y$ 对最左边的列（第 $0$ 列）的瓷砖进行上色，使得瓷砖 $(i,0)$ 的颜色为 $Y[i]$（$0 \leq i < N$）。

然后她重复以下步骤直至所有瓷砖都上色完成：

• 她找到任意一片没有上色的瓷砖 $(i,j)$，其上方相邻的瓷砖 $(i-1, j)$ 和左边相邻的瓷砖 $(i, j-1)$ 都已经上色。
• 然后，如果这两片相邻的瓷砖都是白色，她会把瓷砖 $(i,j)$ 涂成黑色；否则，涂成白色。

可以证明，瓷砖最终的颜色不依赖于 Salma 的上色顺序。

Yasmin 对马赛克瓷砖的颜色非常好奇。她向 Salma 提出 $Q$ 个问题，从 $0$ 到 $Q-1$ 编号。在问题 $k$（$0 \leq k < Q$）中，Yasmin 通过以下信息指定马赛克中的一个长方形：

• 最上面的行 $T[k]$ 和最下面的行 $B[k]$（$0 \leq T[k] \leq B[k] < N$）；
• 最左边的列 $L[k]$ 和最右边的列 $R[k]$（$0 \leq L[k] \leq R[k] < N$）。

问题的答案是该长方形中黑色瓷砖的数量。具体来说，Salma 应当找出有多少片瓷砖 $(i,j)$ 满足 $T[k] \leq i \leq B[k]$，$L[k] \leq j \leq R[k]$，且颜色为黑色。

请编写程序回答 Yasmin 的问题。

实现细节

你要实现以下函数。

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$：长度为 $N$ 的数组，分别描述最上方行和最左边列的瓷砖的颜色。
• $T$，$B$，$L$，$R$：长度为 $Q$ 的数组，分别描述 Yasmin 所提出的问题。
• 该函数应返回一个长度为 $Q$ 的数组 $C$，使得 $C[k]$ 给出问题 $k$（$0 \leq k < Q$）的答案。
• 对每个测试用例，该函数恰好被调用一次。

输入格式

评测程序示例读取如下格式的输入：

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]

输出格式

评测程序示例按照如下格式打印你的答案：

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

其中 $S$ 是 mosaic 所返回的数组 $C$ 的长度。

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

7
3

提示

考虑以下函数调用。

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

该例子如下图所示。左边的图展示了马赛克中瓷砖的颜色，中间和右边的图分别展示了 Yasmin 的第一个问题和第二个问题中的长方形。

这两个问题的答案（即阴影长方形中 1 的个数）分别是 7 和 3。因此，函数应该返回 $[7, 3]$。

约束条件

• $1 \leq N \leq 200\,000$
• $1 \leq Q \leq 200\,000$
• 对所有满足 $0 \leq i < N$ 的 $i$，都有 $X[i] \in \{0, 1\}$，且 $Y[i] \in \{0, 1\}$
• $X[0] = Y[0]$
• 对所有满足 $0 \leq k < Q$ 的 $k$，都有 $0 \leq T[k] \leq B[k] < N$，且 $0 \leq L[k] \leq R[k] < N$

子任务	分数	额外的约束条件
1	$5$	$N \leq 2; Q \leq 10$
2	$7$	$N \leq 200; Q \leq 200$
3		对所有满足 $0 \leq k < Q$ 的 $k$，都有 $T[k] = B[k] = 0$
4	$10$	$N \leq 5000$
5	$8$	对所有满足 $0 \leq i < N$ 的 $i$，都有 $X[i] = Y[i] = 0$
6	$22$	对所有满足 $0 \leq k < Q$ 的 $k$，都有 $T[k] = B[k]$，且 $L[k] = R[k]$
7	$19$	对所有满足 $0 \leq k < Q$ 的 $k$，都有 $T[k] = B[k]$
8	$22$	没有额外的约束条件。