CF1420C2 Pokémon Army (hard version)

这是本题的困难版本。不同之处在于，简单版本中没有交换操作。只有在所有版本都被解决后，你才能进行 hack。 皮卡丘是一只可爱又友善的宝可梦，生活在野生皮卡丘群中。 但最近众所周知，臭名昭著的火箭队想要偷走所有这些宝可梦！宝可梦训练师 Andrew 决定帮助皮卡丘组建一支宝可梦军队来抵抗。 首先，Andrew 数了数所有的宝可梦——一共有 $n$ 只皮卡丘。第 $i$ 只宝可梦的力量值为 $a_i$，且所有这些数都是互不相同的。 作为军队，Andrew 可以选择任意非空子序列的宝可梦。换句话说，Andrew 可以从 $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$。 Andrew 正在尝试调整宝可梦的顺序。他会进行 $q$ 次操作。在第 $i$ 次操作中，Andrew 会交换第 $l_i$ 只和第 $r_i$ 只宝可梦。 Andrew 想知道在初始宝可梦排列下，他能获得的最大军队力量是多少。他还需要知道每次操作后能获得的最大军队力量。 请帮助 Andrew 和宝可梦，否则火箭队就要得逞了！

每个测试点包含多个测试用例。 第一行包含一个正整数 $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 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+4-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$。 由 ChatGPT 4.1 翻译