题目链接

题意：一个无穷数列，从1开始，初始第i个位置上为i，给出n个swap，每次交换两个位置的数。问交换n次以后得到的数列中，逆序对的数。

思路：

官方题解：

题目链接

题意：

how many pairs of integers l and r are there, such that 1 ≤ l < r ≤ n and sequence b = _a_1_a_2... a__l__a__r__a__r + 1... a__n has no more than k inversions.

我花了两个小时才看懂题。。。。一直没懂b数列中a[l]和a[r]怎么就挨着了。。。

题目链接 题意：给出n个数，求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。

思路：对于这种要求三个数满足条件的题目，老司机的经验是考虑中间那个数，这道题也不例外。

题目链接 题意：定义_f_(l, r, x)为区间[l,r]中x出现的次数。现在要求calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such that_f_(1, i, a__i) > f(j, n, a__j).

思路：可以通过o(n)预处理出f(1,i,a[i])和f[j,n,a[j]]，其实预处理的过程就是离散化的过程呢。。。

题目链接

题意：

这题是问一个长度为n的循环数组中，逆序对最少的个数。。。

我们可以先用树状数组求出初始的数列的逆序对。。。

然后其他的可以通过递推得到。。。。