题解

思路推导

对一个固定排列，最大交错子序列和可以写成局部增量之和：令 $a_0=0$，答案为

直观上，每段严格上升区间只需保留区间起点前的低谷和区间末尾的高峰；删除中间元素不会降低答案。把所有上升段的增量相加，正好得到最优交错和。

做法

定义位置 $i$ 的贡献为 $c_i=\max(0,a_i-a_{i-1})$。初始时在线性时间内求出全部贡献之和。

交换位置 $l$ 和 $r$ 后，只有以 $l,l+1,r,r+1$ 为右端点的相邻差可能改变。交换前先从答案中删除这些位置的旧贡献，完成交换后再加入新贡献。位置越界或重复时只处理一次。

正确性证明

把排列分解为若干极大的上升段。任意交错子序列在一段上升区间内部保留多个同号位置都不会优于只保留该段的低谷与高峰，因此最优值等于各上升段“峰值减谷值”的总和；首段的虚拟谷值为 $a_0=0$。这正是所有 $\max(0,a_i-a_{i-1})$ 的和。

一次交换只改变与两个被交换位置相邻的差值，所以除 $l,l+1,r,r+1$ 外的所有贡献保持不变。算法精确删除这些旧贡献并加入新贡献，因此每次输出仍等于当前排列的最大交错子序列和。

复杂度分析

每个测试用例的预处理时间为 $O(n)$，每次交换为 $O(1)$；总时间复杂度为 $O(n+q)$，空间复杂度为 $O(n)$。