CF1392I Kevin and Grid

当 Kevin 在 BigMan 的房子里时，突然一个陷阱把他送到了一个有 $n$ 行 $m$ 列的网格上。 BigMan 的陷阱由两个数组配置：数组 $a_1,a_2,\ldots,a_n$ 和数组 $b_1,b_2,\ldots,b_m$。 在第 $i$ 行有一个加热器，使该行升温 $a_i$ 度，在第 $j$ 列有一个加热器，使该列升温 $b_j$ 度，因此单元格 $(i,j)$ 的温度为 $a_i+b_j$。 幸运的是，Kevin 有一套装备，带有一个参数 $x$ 和两种模式： - 耐热模式：在此模式下，装备可以承受所有温度大于等于 $x$ 的单元格，但一旦进入温度小于 $x$ 的单元格就会被冻结。 - 耐冷模式：在此模式下，装备可以承受所有温度小于 $x$ 的单元格，但一旦进入温度大于等于 $x$ 的单元格就会被烧毁。 一旦 Kevin 落在某个单元格上，如果该单元格温度小于 $x$，装备会自动切换到耐冷模式，否则切换到耐热模式，并且之后无法再更改。 如果两个单元格有公共边，则称它们是相邻的。 一条路径是指一系列单元格 $c_1,c_2,\ldots,c_k$，使得对于 $1 \leq i \leq k-1$，$c_i$ 和 $c_{i+1}$ 是相邻的。 如果存在一条仅包含 Kevin 能够踩到的单元格的路径连接两个单元格，则称这两个单元格是连通的。 一个连通块是一个极大的两两连通的单元格集合。 如果一个连通块包含至少一个网格的边界单元格，则称其为“好”的连通块，否则为“坏”的连通块。 为了评估当前情况，Kevin 会给每个“好”的连通块记 $1$ 分，每个“坏”的连通块记 $2$ 分。 最终得分为温度大于等于 $x$ 的所有连通块得分之和减去温度小于 $x$ 的所有连通块得分之和。 Kevin 有 $q$ 个可能的 $x$ 值，对于每个 $x$，他都想知道最终得分。 请帮助 Kevin 战胜 BigMan！

第一行包含三个整数 $n$、$m$、$q$（$1 \leq n,m,q \leq 10^5$），分别表示行数、列数和 $x$ 的可能取值个数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^5$）。 第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 \leq b_j \leq 10^5$）。 接下来的 $q$ 行，每行包含一个整数 $x$（$1 \leq x \leq 2 \cdot 10^5$）。

输出 $q$ 行，第 $i$ 行输出输入中第 $i$ 个 $x$ 对应的答案。

在第一个样例中，温度小于 $5$ 的连通块得分为 $1+2$，温度大于等于 $5$ 的连通块得分为 $2$。因此，最终得分为 $2-3=-1$。 由 ChatGPT 4.1 翻译