題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 awc0064_e Reduce Inversions with Adjacent Swaps

Problem Statement

題目簡述

給定一個 $1$ 到 $N$ 的排列 $P_1, P_2, \ldots, P_N$ 。
一次操作可以交換相鄰兩張卡片，最多操作 $K$ 次。
操作目標是讓最後排列的逆序對數最小，求可達到的最小逆序對數。

Constraints

約束條件

$1 \leq N \leq 2 \times 10^5$
$0 \leq K \leq 10^{18}$
$(P_1, P_2, \ldots, P_N)$ 是 $(1, 2, \ldots, N)$ 的排列
輸入皆為整數

思路：逆序對計數 + 貪心消除

相鄰交換對逆序對的影響

一次相鄰交換只會改變被交換的兩張卡片之間的相對順序，其他卡片與它們的相對前後關係不會改變。

因此：

若相鄰兩張卡片本來形成逆序，即 $P_i > P_{i+1}$ ，交換後會少掉這一個逆序對。
若相鄰兩張卡片本來是正序，即 $P_i < P_{i+1}$ ，交換後反而會多出一個逆序對。

也就是說，一次相鄰交換對逆序對數的影響一定恰好是 $+1$ 或 $-1$ 。

Tip

若目標是盡量降低逆序對數，每次只需要選擇一組相鄰且逆序的卡片來交換，就能讓答案確實減少 $1$ 。

為什麼可以一直減少到零：氣泡排序的觀點

從氣泡排序的過程來看，當排列還不是升序時，必定存在至少一對相鄰且逆序的卡片。交換這對卡片後，逆序對數就會減少 $1$ 。

因此，最多需要的交換次數就是初始逆序對數 $I$ ，就能把排列變成升序，逆序對數降到 $0$ 。

答案

因此答案就是：

\max(I-K, 0)

複雜度分析

時間複雜度： $\mathcal{O}(N\log N)$
空間複雜度： $\mathcal{O}(N)$

Code

from atcoder.fenwicktree import FenwickTree


def solve():
    n, k = map(int, input().split())
    A = list(map(int, input().split()))

    ans = 0
    bit = FenwickTree(n + 1)
    for x in A:
        ans += bit.sum(x + 1, n + 1)  # [l, r)
        bit.add(x, 1)

    print(max(ans - k, 0))


if __name__ == "__main__":
    solve()