CF1789C Serval and Toxel's Arrays

Toxel 喜欢数组。在前往帕底亚地区旅行前，Serval 送给他一个数组 $a$ 作为礼物。这个数组包含 $n$ 个互不相同的元素。 为了获得更多数组，Toxel 对这个初始数组进行了 $m$ 次操作。在第 $i$ 次操作中，他将第 $(i-1)$ 个数组的第 $p_i$ 个元素修改为 $v_i$，得到第 $i$ 个数组（初始数组 $a$ 编号为 $0$）。在修改过程中，Toxel 保证每次操作后每个数组的元素仍然互不相同。 最终，Toxel 得到了 $m+1$ 个数组，记为 $A_0=a,A_1,\ldots,A_m$。对于每对 $(i,j)$（$0 \le i < j \le m$），Toxel 定义其价值为 $A_i$ 和 $A_j$ 拼接后不同元素的数量。现在 Toxel 想知道，所有数对的价值之和是多少？请帮他计算这个答案。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n,m \le 2 \cdot 10^5$）——数组长度和操作次数。 每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le n+m$）。保证所有 $a_i$ 互不相同。 接下来的 $m$ 行每行包含两个整数 $p_i$ 和 $v_i$（$1 \le p_i \le n$，$1 \le v_i \le n+m$）——被修改元素的位置及其新值。保证每次修改后数组元素仍然互不相同。 保证所有测试用例的 $n$ 之和与 $m$ 之和均不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数——所有数对的价值之和。

在第一个测试用例中，数组变化如下：$[1,2,3] \to [\underline{4},2,3] \to [4,\underline{5},3]$。 $0$ 号数组和 $1$ 号数组拼接后为 $[1,2,3,4,\sout{2},\sout{3}]$，有 $4$ 个不同元素。 $0$ 号数组和 $2$ 号数组拼接后为 $[1,2,3,4,5,\sout{3}]$，有 $5$ 个不同元素。 $1$ 号数组和 $2$ 号数组拼接后为 $[4,2,3,\sout{4},5,\sout{3}]$，有 $4$ 个不同元素。 被划掉的元素表示数组中的重复项。 因此答案为 $4+5+4=13$。 在第二个测试用例中，请注意操作后数组可能保持不变。