CF2163C Monopati

给定一个 $2$ 行 $n$ 列的网格 $a$，其中每个单元格的取值在 $1$ 到 $2n$ 之间。 定义 $f(l, r)$（其中 $1 \le l \le r \le 2n$）：它表示一个 $2$ 行 $n$ 列的二进制$^{\text{∗}}$网格 $b$，满足当且仅当 $l \le a_{i, j} \le r$ 时，$b_{i, j} = 1$。注意，单元格 $(i, j)$ 表示自上向下第 $i$ 行、从左到右第 $j$ 列的单元格。 请统计满足 $1 \le l \le r \le 2n$ 的整数对 $(l, r)$ 的个数，使得在 $f(l, r)$ 中，存在一条由值为 $1$ 的相邻单元格$^{\text{†}}$构成的 **向下-向右** 路径，从单元格 $(1, 1)$ 到 $(2, n)$。 $^{\text{∗}}$ 一个网格当且仅当其每个单元格的取值为 $\mathtt{0}$ 或 $\mathtt{1}$ 时被认为是二进制网格。 $^{\text{†}}$ 向下-向右的相邻路径是指这样一个单元格序列：序列中的每个单元格与前一个单元格要么共享其上边（向下移动），要么共享其左边（向右移动）。

每个测试包含多组测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。随后给出各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——网格的列数。 第二行恰好包含 $n$ 个整数 $a_{1, 1}, a_{1, 2}, \dots, a_{1, n}$（$1 \le a_{1, i} \le 2n$）——网格第一行各单元格的取值。 第三行恰好包含 $n$ 个整数 $a_{2, 1}, a_{2, 2}, \dots, a_{2, n}$（$1 \le a_{2, i} \le 2n$）——网格第二行各单元格的取值。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对每个测试用例，在单独一行输出一个整数，表示满足 $1 \le l \le r \le 2n$ 且在 $f(l, r)$ 中存在一条从 $(1, 1)$ 到 $(2, n)$ 的、由值为 $1$ 的相邻单元格构成的向下-向右路径的整数对 $(l, r)$ 的数量。

考虑第一个样例。 网格 $f(1, 1)$、$f(1, 2)$ 如下： $$ \mathtt{10} $$ $$ \mathtt{01} $$ 从左上角到右下角不存在仅由 $1$ 组成的路径，因此 $(1, 1)$ 与 $(1, 2)$ 不计入答案。 网格 $f(1, 3)$ 与 $f(1, 4)$ 如下： $$ \mathtt{11} $$ $$ \mathtt{11} $$ 由于存在从 $(1, 1)$ 到 $(2, 2)$ 的合法路径，所以 $(1, 3)$ 与 $(1, 4)$ 计入答案。 网格 $f(2, 2)$、$f(4, 4)$ 如下： $$ \mathtt{00} $$ $$ \mathtt{00} $$ 网格 $f(2, 3)$、$f(2, 4)$、$f(3, 3)$、$f(3, 4)$ 如下： $$ \mathtt{01} $$ $$ \mathtt{10} $$ 因此 $(2, 3)$、$(2, 4)$、$(3, 3)$ 与 $(3, 4)$ 均不计入答案。 唯一被计入的配对是 $(1, 3)$ 与 $(1, 4)$，因此答案为 $2$。 Translated by ChatGPT 5.