逆序对

题目链接 题意：一个无穷数列，从1开始，初始第i个位置上为i，给出n个swap，每次交换两个位置的数。问交换 n 次以后得到的数列中，逆序对的个数。 思路： 官方题解： At first find the position of each element which is used in swap (using map). Now let’s find the answer. It consists of the two parts. First part is the number of inversions formed by only whose elements which took part in the swaps. They can be counted by one of the standard ways: mergesort or Fenwick tree. The second part is the number of inversions formed by pairs of elements where one element has been swapped even once, and the other element stayed at his position. Let’s consider the following test:

题目链接 题意： 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]怎么就挨着了。。。 其实意思是。。。只保留a数列中1..l和r..n的。。。构成b数列。。。然后b数列的逆序对数小于等于k.问这样的l,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的循环数组中，逆序对最少的个数。。。 我们可以先用树状数组求出初始的数列的逆序对。。。