Nếu chỉ thực hiện thao tác loại \(2\): Đáp án là số lượng nghịch đảo (số cặp \(i, j\) thoả mãn \(i <j\) và \(a_{i} > a_{j}\)).

Nếu dãy không có nghich đảo thì đáp án là 0.

Do đó để biến đổi ít phép nhất ta cần dùng thao tác \(1\) để chọn ra \(2\) số \(i, j\) sao cho sau khi đổi chỗ \(2\) phần tử này, số lượng nghịch đảo còn lại là ít nhất. Thao tác \(1\) sẽ được thực hiện trước các thao tác \(2\).

Khi đó bài toán đưa về tìm \(2\) số \(i, j\) nghịch đảo, sao cho số lượng \(k\) \((i < k < j, a_{j} < a_{k} < a_{i})\) là lớn nhất. Ta quy ước \(f(i, j) = k\).

Với mỗi \(i\) cố định ta quy ước \(v_{i} = j\) sao cho \(f(i, j)\) lớn nhất.

Cặp \((i, j)\) có thể là đáp án ó \(a_{i}\) là lớn nhất trong đoạn từ \(1 \rightarrow i\). (ta gọi đây là điều kiện \(( * )\))

Do đó ta chỉ xét những số \(i\) thỏa mãn điều kiện \(( * )\).

Xét \(2\) số \(i, j\) \((i < j)\) thỏa mãn điều kiện \(( * )\), khi đó \(v_{i} \leq v_{j}\).

Đến đây ta có thể dùng chia để trị để giới hạn số cặp phải xét là \(n \times \log_{2}(n)\).

Dùng cây Fenwick Tree để đếm tính \(f(i, j)\).
Sau khi tìm được \(i, j\) ta đổi chỗ \(2\) phần tử này.

Đáp án cuối cùng là số lượng nghịch đảo của dãy sau khi đổi chỗ \(i, j\) cộng thêm \(1\).

Độ phức tạp \(\mathcal{O}(n \times \log_{2} (n)^2)\).

· Khi dùng cây Fenwick Tree, ta luôn lưu \(2\) con trỏ \(l, r\) sao cho khi xét đến \(f(i, j)\) thì \(l = i, r = j\). Do ta dùng chia để trị lên số bước dịch chuyển \(2\) con trỏ \(l, r\) tối đa là \(n \times \log_{2}(n)\) bước.