# codeforces 540 E. Infinite Inversions (分类思想+线段树求逆序对)

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:

2

2 6

4 8

The global sequence will look as follows: [1 6 3 8 5 2 7 4 9 …], and here is the array of swapped elements: [6 8 2 4].

Let’s understand with which numbers the number 8 forms the inversions. The only elements that could do that are the elements between the initial position of the number 8 (where the number 4 is now) and its current position: [5 2 7]. There are two numbers on this segment which didn’t take part in swaps: 5 and 7. The number 2 should not be counted as it took part in the swaps and we have already counted it in the first part of the solution.

So we should take the count of numbers between 8’s indices in the global sequence (8 - 4 - 1 = 3) and subtract the count of numbers between its indices in the swaps array (4 - 2 - 1 = 1)(在交换序列中【6,8,2,4】4的位置在4,8的位置在2). We’ll get the number of inversions formed by the element 8 and the elements which haven’t moved at all, it’s 2. Counting this value for all elements which have been swapped at least once, we get the second part of the answer. All operations in the second part of the solution can be performed using sorts and binary searches.

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:

f[i]表示交换序列中，离散化后，处于第i个位置上面的值（也是离散化之前的位置）

p[i]表示现在在i位置上的数初始是在p[i]位置(位置是离散化后的从小到大的顺序，因此是对于交换序列的（因为只有交换序列才离散化了））

### 说点什么 