CF1789C.Serval and Toxel's Arrays
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 pi -th element of the (i−1) -th array to vi , 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 A0=a,A1,…,Am . For each pair (i,j) ( 0≤i<j≤m ), Toxel defines its value as the number of distinct elements of the concatenation of Ai and Aj . 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≤t≤104 ). The description of the test cases follows.
The first line of each test case contains two integers n and m ( 1≤n,m≤2⋅105 ) — the length of the array and the number of operations.
The second line of each test case contains n integers a1,a2,…,an ( 1≤ai≤n+m ). It is guaranteed that all ai are pairwise distinct.
Each of the next m lines of each test case contains two integers pi and vi ( 1≤pi≤n , 1≤vi≤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⋅105 .
输出格式
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]→[4,2,3]→[4,5,3] .
The concatenation of the 0 -th array and the 1 -st array is [1,2,3,4,2,3] . There are 4 distinct elements.
The concatenation of the 0 -th array and the 2 -nd array is [1,2,3,4,5,3] . There are 5 distinct elements.
The concatenation of the 1 -st array and the 2 -nd array is [4,2,3,4,5,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.