P11053 [IOI 2024] 马赛克上色

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

无

无

考虑以下函数调用。 ``` 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 | $7$ | 对所有满足 $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$ | 没有额外的约束条件。