顺心荷花

文章
6
资源
0
加入时间
2年10月24天

Codeforces 540E Infinite Inversions 离散化+树状数组

题意:有一个无限长序列。进行n次操作,每次把下标为i, j的两个值交换。最后问你整个序列的逆序数的个数。思路:求逆序数分为两部分。一部分是交换过位置的,另一部分是没有交换过的。第一部分:用map处理n次操作后的情况。离散化后,利用树状数组求出交换过的位置的逆序数的个数。第二部分:看一个样例:21 69 5得到的序列为6 2 3 4