题目描述

给定两个长度均为 $m$ 的数组 $x$ 和 $y$，设 $z$ 是另一个长度为 $m$ 的数组，且 $z$ 每个位置的前缀最大值与 $x$ 对应位置的前缀最大值相同。形式化地说，需满足对所有 $1 \leq i \leq m$，都有 $\max(x_1,x_2,\ldots,x_i) = \max(z_1,z_2,\ldots,z_i)$。

定义 $f(x,y)$ 为：在所有满足上述条件的数组 $z$ 中，$z_i = y_i$ 的位置的最大数量。

现给定两个长度均为 $n$ 的整数序列 $a$ 和 $b$，请计算双重求和 $\sum_{l=1}^n \sum_{r=l}^n f\left( a[l..r], b[l..r] \right)$ 的结果。其中 $a[l..r]$ 表示数组 $a$ 中从第 $l$ 个元素到第 $r$ 个元素的子数组（即 $[a_l,a_{l+1},\ldots,a_r]$），$b[l..r]$ 表示数组 $b$ 中从第 $l$ 个元素到第 $r$ 个元素的子数组（即 $[b_l,b_{l+1},\ldots,b_r]$）。

输入格式

每组测试包含多组测试用例。第一行输入测试用例的数量 $t$（$1 \leq t \leq 10^4$），随后依次描述每组测试用例。

每组测试用例的输入格式如下：

• 第一行：一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）
• 第二行：$n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 2 \cdot n$）
• 第三行：$n$ 个整数 $b_1,b_2,\ldots,b_n$（$1 \leq b_i \leq 2 \cdot n$）

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每组测试用例，输出一个整数——即上述双重求和的结果。

（注：英文原题面中“the final value of $f(a)$ assuming both players play optimally”为笔误，结合题目描述与样例，实际需输出上述双重求和结果）

样例

6
3
5 3 1
4 2 1
5
1 2 3 4 5
1 2 3 4 5
6
7 1 12 10 5 8
9 2 4 3 6 5
1
1
2
6
5 1 2 6 3 4
3 1 6 5 2 4
2
2 2
1 1

5
35
26
0
24
1

样例说明

在第一个测试用例中，答案是以下各项的和：

• $f(a[1..1], b[1..1]) = f([5],[4]) = 0$，此时使用的 $z$ 数组为 $[5]$；
• $f(a[2..2], b[2..2]) = f([3],[2]) = 0$，此时使用的 $z$ 数组为 $[3]$；
• $f(a[3..3], b[3..3]) = f([1],[1]) = 1$，此时使用的 $z$ 数组为 $[1]$；
• $f(a[1..2], b[1..2]) = f([5,3],[4,2]) = 1$，此时使用的 $z$ 数组为 $[5,2]$；
• $f(a[2..3], b[2..3]) = f([3,1],[2,1]) = 1$，此时使用的 $z$ 数组为 $[3,1]$；
• $f(a[1..3], b[1..3]) = f([5,3,1],[4,2,1]) = 2$，此时使用的 $z$ 数组为 $[5,2,1]$。

来源

Codeforces 2137F，英文题名 Prefix Maximum Invariance。