← 返回题目列表

Codeforces · 1420/C2

C2. 神奇宝贝军团(困难版)

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

这是问题的困难版本。版本之间的区别在于简易版本没有交换操作。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

皮卡丘是一只可爱又友善的神奇宝贝,生活在野生皮卡丘群中。

但最近人们知道,臭名昭著的 R 队想要偷走所有这些神奇宝贝!神奇宝贝训练师安德鲁决定帮助皮卡丘建立一支神奇宝贝军队来抵抗。

首先,Andrew 数了数所有神奇宝贝 — 正好有 $$$n$$$ 皮卡丘。第 $$$i$$$ 个神奇宝贝的强度等于 $$$a_i$$$,并且所有这些数字都是不同的。

作为一支军队,安德鲁可以选择任何非空的神奇宝贝子序列。换句话说,安德鲁从 $$$k$$$ 索引中选择一些数组 $$$b$$$ ,使得 $$$1 \le b_1 < b_2 < \dots < b_k \le n$$$ ,他的军队将由具有 $$$a_{b_1}, a_{b_2}, \dots, a_{b_k}$$$ 力量的神奇宝贝组成。

军队的兵力等于子序列元素的交替和;也就是说,$$$a_{b_1} - a_{b_2} + a_{b_3} - a_{b_4} + \dots$$$。

安德鲁正在尝试神奇宝贝顺序。他执行$$$q$$$操作。在第$$$i$$$操作中,安德鲁交换了第$$$l_i$$$和第$$$r_i$$$个神奇宝贝。

安德鲁想知道他在初始神奇宝贝放置时可以达到的军队的最大力量。他还需要知道每次手术后的最大力量。

帮助安德鲁和神奇宝贝,否则 R 队将实现他们的棘手计划!

输入

每个测试包含多个测试用例。

第一行包含一个正整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) 表示测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 3 \cdot 10^5, 0 \le q \le 3 \cdot 10^5$$$) 分别表示神奇宝贝的数量和操作的数量。

第二行包含 $$$n$$$ 不同的正整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) 表示神奇宝贝的优势。

最后 $$$q$$$ 行中的第 $$$i$$$ 行包含两个正整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) 表示在第 $$$i$$$ 操作中交换的神奇宝贝的索引。

保证所有测试用例的$$$n$$$总和不超过$$$3 \cdot 10^5$$$,所有测试用例的$$$q$$$总和不超过$$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$q+1$$$ 整数:交换之前和每次交换之后的军队最大兵力。

示例

输入 #1

3
3 1
1 3 2
1 2
2 2
1 2
1 2
1 2
7 5
1 2 5 4 3 6 7
1 2
6 7
3 4
1 2
2 3

输出 #1

3
4
2
2
2
9
10
10
10
9
11

注意

我们看第三个测试用例:

最初我们可以这样建立一支军队:[1 2 5 4 3 6 7],它的兵力将是$$$5-3+7=9$$$。

第一次操作后,我们可以这样建立一支军队:[2 1 5 4 3 6 7],其兵力将为$$$2-1+5-3+7=10$$$。

第二次操作后我们可以这样建立一支军队:[2 1 5 4 3 7 6],其兵力将为$$$2-1+5-3+7=10$$$。

第三次操作后,我们可以这样建立一支军队:[2 1 4 5 3 7 6],其兵力将为$$$2-1+5-3+7=10$$$。

第四次操作后,我们可以这样建立一支军队:[1 2 4 5 3 7 6],其兵力将为$$$5-3+7=9$$$。

完成所有操作后,我们可以这样建立一支军队:[1 4 2 5 3 7 6],其力量将为$$$4-2+5-3+7=11$$$。