Overview

Find the minimum number of adjacent element swaps needed to sort a given permutation.

Analysis

This problem asks us to count the number of inversions required to sort the array in ascending order.

An inversion is an “improper pair” where a smaller number appears to the right of a larger number that should be to its left. For example, in the array \([3, 1, 2]\), there are 2 inversions: \((3, 1)\) and \((3, 2)\).

Each operation of swapping two adjacent elements corresponds to resolving exactly one inversion. Therefore, to sort the entire array, exactly as many operations as the number of inversions are needed.

A naive approach (simulating adjacent swaps like bubble sort) takes \(O(N^2)\) in the worst case, which would result in TLE given the constraint \(N \leq 2 \times 10^5\).

To efficiently count the number of inversions, we use a merge sort-based algorithm. This is a type of divide-and-conquer approach that can count inversions while sorting.

Algorithm

The flow of the algorithm for counting inversions using merge sort is as follows:

1. Recursively divide the array in half.
2. Assume the left and right subarrays are each sorted, then merge them.
3. During the merge, when an element from the right subarray comes before an element from the left subarray, we know that there are as many inversions as the number of remaining elements in the left subarray at that point.
4. By summing up these counts, we obtain the total number of inversions.

For example, if the left half is \([1, 4, 5]\) and the right half is \([2, 3]\), when we first pick 2 from the right, both 4 and 5 from the left will come after it, so we count 2 inversions.

In this way, we can efficiently count inversions during the merge sort process.

Complexity

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• The merge_sort_and_count_inversions function is called recursively and counts inversions during the merge step.
• The key point is adding the number of remaining elements in the left subarray, len(left) - i.
• Python has a recursion depth limit, so care is needed for very large \(N\), but this is not an issue under the given constraints.

## Source Code

```python
def merge_sort_and_count_inversions(arr):
    if len(arr) <= 1:
        return arr, 0

    mid = len(arr) // 2
    left, inv_left = merge_sort_and_count_inversions(arr[:mid])
    right, inv_right = merge_sort_and_count_inversions(arr[mid:])
    
    merged = []
    i = j = 0
    inv_split = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inv_split += len(left) - i
            j += 1
            
    merged.extend(left[i:])
    merged.extend(right[j:])
    
    return merged, inv_left + inv_right + inv_split

n = int(input())
a = list(map(int, input().split()))

_, inversions = merge_sort_and_count_inversions(a)
print(inversions)

This editorial was generated by qwen3-coder-480b.