← 返回题目列表

Codeforces · 1789/C

C. Serval 和 Toxel 的阵列

中文机器翻译题面 查看原题

Toxel 喜欢数组。在前往帕尔迪亚地区之前,薮猫送给他一个阵列$$$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}$$$ 连接的不同元素的数量。现在托克塞尔想知道,所有对的值的总和是多少?请帮他算出答案。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量$$$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$$$ 个数组的串联为 $$$\require{cancel}[1,2,3,4,\cancel{2},\cancel{3}]$$$。有 $$$4$$$ 不同的元素。

第 $$$0$$$ 个数组和第 $$$2$$$ 个数组的串联是 $$$\require{cancel}[1,2,3,4,5,\cancel{3}]$$$。有 $$$5$$$ 不同的元素。

$$$1$$$-st 数组和 $$$2$$$-nd 数组的串联是 $$$\require{cancel}[4,2,3,\cancel{4},5,\cancel{3}]$$$。有 $$$4$$$ 不同的元素。

删除线元素在数组中是重复的。

因此,答案是$$$4+5+4=13$$$。

在第二个测试用例中,请注意,数组在操作后可能保持不变。