P2448 无尽的生命
题目传送门题意简述
看到题目显而易见是求逆序对个数。
思路分析
看到数据范围 \(x_i,y_i \le 2^{31}-1\)，\(k \le 10^5\)。数据值域大但是个数少，且与数据之间的大小关系有关，因此考虑离散化。
离散化简单介绍
离散化实际就是一种映射，当数据值域过大而个数有限时，可以尝试离散化。
具体过程以此题为例。假设给出这么一组数据
2
123456789 123456
987654321 123456首先将所有出现过的数收集起来，存进 \(a\) 数组，并进行排序，然后再去重保存进 \(pos\) 数组当中。
https://cdn.luogu.com.cn/upload/image_hosting/wykzmz13.png
接下来就可以建立映射关系。将数值大的数在 \(num\) 数组中用数值小的数代替，但各个数之间的大小关系不变，接下来交换操作先用二分答案在 \(pos\) 数组中检索，然后通过映射在 \(num\) 数组中进行交换。
https://cdn.luogu.com.cn/upload/image_hosting/ji9dhfzo.png
最终被交换过的数之间的逆序对在 \(num\) 数组中求即可。
被交换的数与未被交换的数之间的逆序对
考虑每个被交换的数对答案的贡献。
设 \(x
页:
[1]