Serval and Toxel's Arrays

题意翻译

给你一个零时刻的长度为 $n$ 的数组 $a_i$。 时刻 $i\ (1 \le i \le m)$ 的数组是在时刻 $i-1$ 的基础上把位置 $p_i$ 的数改成 $v_i$ 得到的。 现在让你求出 $\sum_{i=0}^m \sum_{j=i+1}^m f(i,j)$，其中 $f(i,j)$ 的值为时刻 $i$ 和时刻 $j$ 的数组拼起来后一共有几种数字。 Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)

题目描述

Toxel likes arrays. Before traveling to the Paldea region, Serval gave him an array $ a $ as a gift. This array has $ n $ pairwise distinct elements. In order to get more arrays, Toxel performed $ m $ operations with the initial array. In the $ i $ -th operation, he modified the $ p_{i} $ -th element of the $ (i-1) $ -th array to $ v_{i} $ , resulting in the $ i $ -th array (the initial array $ a $ is numbered as $ 0 $ ). During modifications, Toxel guaranteed that the elements of each array are still pairwise distinct after each operation. Finally, Toxel got $ m+1 $ arrays and denoted them as $ A_{0}=a, A_{1},\ldots,A_{m} $ . For each pair $ (i,j) $ ( $ 0\le i<j\le m $ ), Toxel defines its value as the number of distinct elements of the concatenation of $ A_{i} $ and $ A_{j} $ . Now Toxel wonders, what is the sum of the values of all pairs? Please help him to calculate the answer.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\le t\le10^{4} $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1\le n,m\le2\cdot10^{5} $ ) — the length of the array and the number of operations. The second line of each test case contains $ n $ integers $ a_{1},a_{2},\dots,a_{n} $ ( $ 1\le a_{i}\le n+m $ ). It is guaranteed that all $ a_i $ are pairwise distinct. Each of the next $ m $ lines of each test case contains two integers $ p_{i} $ and $ v_{i} $ ( $ 1\le p_{i}\le n $ , $ 1\le v_{i}\le n+m $ ) — the position of the modified element and its new value. It is guaranteed that the elements of each array are still pairwise distinct after each modification. It is guaranteed that the sum of $ n $ and the sum of $ m $ over all test cases do not exceed $ 2\cdot10^{5} $ .

输出格式

For each test case, print a single integer — the sum of the values of all pairs of arrays.

输入输出样例

输入样例 #1

3
3 2
1 2 3
1 4
2 5
1 1
1
1 1
10 10
4 6 9 12 16 20 2 10 19 7
1 3
5 4
2 17
2 18
6 11
7 1
8 17
5 5
5 5
2 2

输出样例 #1

13
1
705

说明

In the first test case, the arrays change as follows: $ [1,2,3]\to[\underline{4},2,3]\to[4,\underline{5},3] $ . The concatenation of the $ 0 $ -th array and the $ 1 $ -st array is $[1,2,3,4,\sout{2},\sout{3}]$ . There are $ 4 $ distinct elements. The concatenation of the $ 0 $ -th array and the $ 2 $ -nd array is $[1,2,3,4,5,\sout{3}] $ . There are $ 5 $ distinct elements. The concatenation of the $ 1 $ -st array and the $ 2 $ -nd array is $[4,2,3,\sout{4},5,\sout{3}] $ . There are $ 4 $ distinct elements. Strikethrough elements are duplicates in the array. Therefore, the answer is $ 4+5+4=13 $ . In the second test case, note that the array may remain unchanged after operations.

**标题：Serval and Toxel's Arrays**

**题意翻译：**
给你一个长度为 $ n $ 的数组 $ a_i $ 在零时刻。在时刻 $ i (1 \le i \le m) $ 的数组是基于时刻 $ i-1 $ 的数组，将位置 $ p_i $ 的数改成 $ v_i $ 得到的。现在要你求出 $\sum_{i=0}^m \sum_{j=i+1}^m f(i,j)$，其中 $ f(i,j) $ 的值是时刻 $ i $ 和时刻 $ j $ 的数组拼接起来后总共有几种不同的数字。

**题目描述：**
Toxel 喜欢数组。在去帕尔迪亚地区之前，Serval 送给他一个有 $ n $ 个成对不同的元素的数组 $ a $ 作为礼物。为了得到更多的数组，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
**输入输出格式：**

**输入格式：**
每个测试包含多个测试用例。第一行包含测试用例数 $ t (1\le t\le10^4) $。测试用例描述如下。

每个测试用例的第一行包含两个整数 $ n $ 和 $ m (1\le n,m\le2\cdot10^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\cdot10^5 $。

**输出格式：**
对于每个测试用例，打印一个整数 —— 所有数对数组的值的总和。

**输入输出样例：**

**输入样例 #1：**
```
3
3 2
1 2 3
1 4
2 5
1 1
1
1 1
10 10
4 6 9 12 16 20 2 10 19 7
1 3
5 4
2 17
2 18
6 11
7 1
8 17
5 5
5 5
2 2
```

**输出样例 #1：**
```
13
1
705
```

**说明：**
在第一个测试用例中，数组的变化如下：$ [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 $。

在第二个测试用例中，注意数组在操作后可能保持不变。**标题：Serval and Toxel's Arrays** **题意翻译：** 给你一个长度为 $ n $ 的数组 $ a_i $ 在零时刻。在时刻 $ i (1 \le i \le m) $ 的数组是基于时刻 $ i-1 $ 的数组，将位置 $ p_i $ 的数改成 $ v_i $ 得到的。现在要你求出 $\sum_{i=0}^m \sum_{j=i+1}^m f(i,j)$，其中 $ f(i,j) $ 的值是时刻 $ i $ 和时刻 $ j $ 的数组拼接起来后总共有几种不同的数字。 **题目描述：** Toxel 喜欢数组。在去帕尔迪亚地区之前，Serval 送给他一个有 $ n $ 个成对不同的元素的数组 $ a $ 作为礼物。为了得到更多的数组，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