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