UOJ Logo Universal Online Judge

UOJ

#903. 【IOI2024】马赛克上色

附件下载 统计

题目描述

Salma 想给墙上的粘土马赛克上色。该马赛克由 N×N 片正方形瓷砖组成,共有 N2 片瓷砖;每片瓷砖的尺寸为 1×1,都还没有上色。马赛克从上到下每行瓷砖的行编号从 0N1,从左到右每列瓷砖的列编号从 0N1。位于第 i 行第 j 列(0i<N0j<N)的瓷砖记为 (i,j)。每片瓷砖要么涂成白色(记为 0),要么涂成黑色(记为 1)。

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

然后她重复以下步骤直至所有瓷砖都上色完成: 她找到任意一片没有上色的瓷砖 (i,j),其上方相邻的瓷砖 (i1,j) 和左边相邻的瓷砖 (i,j1)已经上色 然后,如果这两片相邻的瓷砖都是白色,她会把瓷砖 (i,j) 涂成黑色;否则,涂成白色。

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

Yasmin 对马赛克瓷砖的颜色非常好奇。她向 Salma 提出 Q 个问题,从 0Q1 编号。在问题 k0k<Q)中,Yasmin 通过以下信息指定马赛克中的一个长方形: 最上面的行 T[k] 和最下面的行 B[k]0T[k]B[k]<N); 最左边的列 L[k] 和最右边的列 R[k]0L[k]R[k]<N)。

问题的答案是该长方形中黑色瓷砖的数量。具体来说,Salma 应当找出有多少片瓷砖 (i,j) 满足 T[k]iB[k]L[k]jR[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)
  • XY:长度为 N 的数组,分别描述最上方行和最左边列的瓷砖的颜色。
  • TBLR:长度为 Q 的数组,分别描述 Yasmin 所提出的问题。
  • 该函数应返回一个长度为 Q 的数组 C,使得 C[k] 给出问题 k0k<Q)的答案。
  • 对每个测试用例,该函数恰好被调用一次。

约束条件

  • 1N200000
  • 1Q200000
  • 对所有满足 0i<Ni,都有 X[i]{0,1},且 Y[i]{0,1}
  • X[0]=Y[0]
  • 对所有满足 0k<Qk,都有 0T[k]B[k]<N,且 0L[k]R[k]<N

子任务

子任务 分数 额外的约束条件
1 5 N2;Q10
2 7 N200;Q200
3 7 对所有满足 0k<Qk,都有 T[k]=B[k]=0
4 10 N5000
5 8 对所有满足 0i<Ni,都有 X[i]=Y[i]=0
6 22 对所有满足 0k<Qk,都有 T[k]=B[k],且 L[k]=R[k]
7 19 对所有满足 0k<Qk,都有 T[k]=B[k]
8 22 没有额外的约束条件。

例子

考虑以下函数调用。

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

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

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

评测程序示例

输入格式:

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]

其中 Smosaic 所返回的数组 C 的长度。

时间限制:1s

空间限制:2048MB