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

🔗 P1966 [NOIP 2013 提高组] 火柴排队

Problem Statement

題目簡述

給定兩個長度為 nn 的序列 AA 和 BB。每次操作可以交換序列中相鄰的兩個元素。
目標是透過最少次數的交換，使得 ∑i=1n(Ai−Bi)2\sum_{i=1}^n (A_i - B_i)^2 最小。
輸出最少交換次數對 108−310^8 - 3 取模的結果。

Constraints

約束條件

  • 1≤n≤1051 \le n \le 10^5
  • 0≤Ai,Bi≤231−10 \le A_i, B_i \le 2^{31}-1
  • 序列中的元素互不相同。

思路：排序不等式與逆序對

1. 先找出最小化後應該長什麼樣子

題目要最小化：

∑i=1n(Ai−Bi)2\sum_{i=1}^n (A_i - B_i)^2

把平方展開：

∑i=1n(Ai−Bi)2=∑i=1nAi2+∑i=1nBi2−2∑i=1nAiBi\sum_{i=1}^n (A_i - B_i)^2 = \sum_{i=1}^n A_i^2 + \sum_{i=1}^n B_i^2 - 2 \sum_{i=1}^n A_iB_i

不管怎麼交換，相同序列內的元素集合都不會改變，所以 ∑Ai2\sum A_i^2 和 ∑Bi2\sum B_i^2 都是固定的。真正會影響答案的，只剩下每個位置上兩個元素相乘後的總和。

因此，原問題等價於：讓 ∑AiBi\sum A_iB_i 盡可能大。

根據排序不等式（Rearrangement Inequality），兩個序列按照相同大小順序配對時，乘積和最大。也就是說，最終應該讓第 kk 小的火柴與另一排第 kk 小的火柴站在同一個位置。

證明

只要證明「大小順序相同的配對不會更差」即可。

考慮兩根來自第一排的火柴，高度滿足 x<yx < y；再考慮兩根來自第二排的火柴，高度滿足 u<vu < v。

若交叉配對，乘積和為：

xv+yuxv + yu

若按大小順序配對，乘積和為：

xu+yvxu + yv

比較兩者：

(xu+yv)−(xv+yu)=(y−x)(v−u)>0(xu + yv) - (xv + yu) = (y - x)(v - u) > 0

因此，當兩對火柴的相對大小順序不一致時，把它們交換成相同順序，一定能讓乘積和變大。

不斷消除這種「大小順序相反」的配對後，最後得到的就是兩排都按相同排名配對的狀態，也就是第 kk 小配第 kk 小。此時 ∑AiBi\displaystyle \sum A_iB_i 最大，所以原本的平方差總和最小。

2. 把兩排火柴都轉成排名排列

因為兩個序列內的元素都互不相同，所以每個元素都有唯一排名，我們可以把兩排火柴都轉成 11 到 nn 的排名排列：最小的是 11，第二小的是 22，依此類推。

轉換後，問題就變成：透過相鄰交換，讓兩個排名排列在每個位置上相同，並且交換次數最少。

3. 固定第一排，轉化問題為求逆序對數量

由於同時操作兩個排列很麻煩，我們可以固定第一個排列，把它當作「正確的順序」。接著考慮要如何透過最小的相鄰交換次數，第二個排列調整成和第一個排列相同的順序。

當第一個排列恰好是 [1,2,…,n][1, 2, \ldots, n] 的有序排列時，這個問題就變成了：使用相鄰交換對第二個排列做排序的最少操作次數，這正是求第二個排列的逆序對數量。

那麼我們只需要將第一個陣列映射為 [1,2,…,n][1, 2, \ldots, n] 的形式，並對第二個陣列做同樣的映射，便能將問題轉換為「求逆序對數量」的問題。

為什麼是逆序對？

相鄰交換只能改變兩個相鄰元素的先後關係。

如果在目標順序中，某個原本較靠右的位置需要排到較靠左的位置前面，那麼這一對元素的相對順序就是錯的，必須透過一次次相鄰交換跨過彼此。

每一對錯誤的相對順序都至少需要被交換一次，而每次交換相鄰且順序錯誤的兩個元素，也剛好會消除一個逆序對。因此最少相鄰交換次數等於逆序對數量。

結論

將某個排列透過相鄰交換變成另一個排列的最少交換次數，可以轉換成「求逆序對數量」的問題。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)
  • 空間複雜度：O(n)\mathcal{O}(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class BIT:
    __slots__ = ["tree"]

    def __init__(self, n: int):
        self.tree = [0] * (n + 1)

    def add(self, k: int, x: int) -> None:
        while k < len(self.tree):
            self.tree[k] += x
            k += k & -k

    def preSum(self, k: int) -> int:
        res = 0
        while k > 0:
            res += self.tree[k]
            k -= k & -k
        return res

    def query(self, l: int, r: int) -> int:
        if l > r:
            return 0
        return self.preSum(r) - self.preSum(l - 1)


def solve():
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    MOD = int(1e8) - 3

    # 將 A 和 B 離散化，按照大小映射到 [1, n] 的整數
    mp1 = {x: i for i, x in enumerate(sorted(A), start=1)}
    mp2 = {x: i for i, x in enumerate(sorted(B), start=1)}
    A = [mp1[x] for x in A]
    B = [mp2[x] for x in B]

    # 把一個亂序的排列透過相鄰交換變成有序的操作次數，等同於求逆序對的數量
    # 把 A 再按照位置映射為 [1, n]，並做 B 做同樣的映射，則就等同於上述求逆序對的問題
    mp = {x: i for i, x in enumerate(A, start=1)}

    ans = 0
    bit = BIT(n)
    for x in B:
        ans = (ans + bit.query(mp[x] + 1, n)) % MOD
        bit.add(mp[x], 1)
    print(ans)


if __name__ == "__main__":
    solve()