暑假集训 Day7 总结

前言：

今天只 AC 了一道题，最难受的是，第三题我公式都推出来了，但是被逆序对的差之和卡住了，难绷。另外，我个人认为 楼兰图腾 这道题用处是真的大，一定要吃透，很有帮助。

B.嫉妒的两人

除了转化题目，其他的都不难，还有，要加离散化。

正解思路：

这道题要先把它转化一下，先把数组排序一下，按照 $a$ 数组从小到大，如果两数相等，就按 $b$ 数组从大到小排序。 接下来，我们要对 $b$ 数组进行离散化，因为 $b_i\le 10^9$，数据太大了。接下来，我们枚举每一个中间点，求出它后面有多少个 $a_i$ 和 $a_{i+1}$ 相等同时 $b_i$ 和 $b_{i+1}$ 相等，记为 $cnt$。于是，我们可以按照 $\dfrac{1}{4}$ 楼兰图腾 去做，看看前面有多少个比当前的 $b_i$ 大，记为 $num$，就可以组成 $num \times cnt+cnt^2$ 个方案，最后输出答案即可。

C.双倍求和

这道题尤为可惜，考场上推出了公式，但被逆序对卡成了 $27$ 分 TLE，比暴力拿的分还少。

正解思路 $1$：

首先，题目给的公式固然是不可用的：

$$\sum_{i=1}^n\sum_{j=i+1}^n \max\left(a_j-a_i,0\right)$$

接下来我们把公式展开，变为：

$$[(a_n-a_1)+(a_{n-1}-a_1)+(a_{n-2}-a_1)+\dots+(a_2-a_1)]+[(a_n-a_2)+(a_{n-1}-a_2)+\dots+(a_3-a_2)]+[(a_n-a_3)+(a_{n-1}-a_3)+\dots+(a_4-a_3)]+\dots+[(a_n-a_{n-1})]$$

我们可以画个图：

可以发现，我们要求的答案就是红色减去蓝色部分。

推出求红色的公式：

$$\left(\sum_{i=1}^n a_i\right)\times (i-1)$$

再推出算蓝色部分的公式：

$$\sum_{i=1}^{n-1} a_i\times (n-i)$$

但由于目前还是要求逆序对的差之和，很麻烦，我们先对 $a$ 数组排序，然后就可以直接用红色减蓝色部分的就可以了。 最终答案为:

$$\left(\sum_{i=1}^n a_i\right)\times (i-1)-\sum_{i=1}^{n-1} a_i\times (n-i)$$

由于求这个答案不用双重 for 循环，直接算就可以了。

正解思路 $2$：

用两个树状数组，一个存储值，一个存储个数。根据上面推的公式，解决即可。注意：一定要离散化，不然会爆炸。

D.矩阵操作

正解思路:

这道题比较复杂，主要是有那个操作二，十分的恶心，会让之前所有的操作一白费，而且，由于数据范围比较大，有 $2\times 10^5$ 所以也不可以建立矩阵直接计算。那么我们就要想一种办法解决这种情况。我们发现，每一次的操作二只会影响前面的操作一，所以，我们可以记录每一次的操作二在什么时候出现。每出现一次操作一，加上即可；出现操作二，记录当前行最后一次出现操作二的时间；遇见操作三，在最后输出答案前，减去当前行最后出现操作二之前的操作一的值，最后输出即可。

E.交换

正解思路：

这道题目其实比较简单，但首先，我们要把原数组转化一下，把 $a_i$ 和 $b_i$ 都加上 $i$。因为原数加上下标就是这个数的永恒值，不管这个数交换到了哪里，这个数都不会变。首先，我们先判断是否有答案，这一步很简单，只用判断两个数组中排序后每一个元素的永恒值是否相等，如果相等，则有答案，后续再求，否则输出 $-1$。这一步的可行是可以证明的，如果两数的的永恒值相等，那么两数一定可以通过任意次交换变为全等，数组也一样。接下来，我们开始算答案。我们先枚举两个数组的其中一个，找到其中一个数组中所有值在另一个数组中的位置，也就是这个数要移动到的位置，用一个新的数组统计。最后，我们只需要对新数组求逆序对，就可以知道操作次数了。