题解
因为有这个操作：将序列 \(a\) 加上 \(\{n, n - 1, \cdots, 1\}\)，考虑差分。
那么显然每次操作会将差分数组中的每个元素减去 \(1\)，如果差分数组中有 \(0\)，就会把 \(0\) 删除。
所以可以发现差分数组中剩下的一定是操作前的最大值。
由于操作后最大值还是最大值，最小值仍然是最小值，所以答案是 原序列最大值+差分数组最大值。
考虑用 multiset 维护原序列和差分，当有一次修改操作（将 \(x \to y\)），我们更新 multiset：
- 求出 \(x\) 在原序列中的前驱与后继。
- 在维护差分数组的
multiset中删除 \(x\) 与前驱的差和 \(x\) 与后继的差。 - 在原序列的
multiset中插入 \(y\)。 - 加入 \(y\) 与它前驱的差与 \(y\) 与它后继的差。
然后就没了。
code: