一回来就吃屎。

A：

唯一的唐题。

对 a 建个线性基，把除了关键点以外的所有数先整出来，之后就是关键点内部搞，将对应矩阵消成上三角矩阵，使得每个点不会后面产生影响。

B：

首先答案是 :

$$\left(\sum_{i=1}^{n}\left|a_{i}-p_{i}\right|\right)+C \times(n-\text { 置换环个数 })$$

交换两个数最多增加一个置换环，因此是 $(n-置换环个数)$ 次操作。下面给出一种构造：
对于两个位置 $i, j$ ，想要再交换过后仍能达到最优解，需要满足:

$$a_{i} \in\left[\min \left(a_{j}, p_{j}\right), \max \left(a_{j}, p_{j}\right)\right], a_{j} \in\left[\min \left(a_{i}, p_{i}\right), \max \left(a_{i}, p_{i}\right)\right]$$

证明考虑讨论绝对值的情况即可。

对于每个置换环分开考虑。

我们把当前环中 $p$ 最小的位置拿出来，设为 $i$ ，那么 $j$ 满足条件 $a_{j} \geq p_{i}, p_{j}>p_{i}$ 。

优秀的查找方式是从 $i$ 出发，维护两个指针，一个往顺时针走，一个往逆时针走，直到其中一个找到了这个 $j$ 。

注意到这样找到这个环的次数是新的两个环中环长的较小值，所以复杂度是 $\mathcal O(n \log n)$ 的。

C：

没。