Luogu 🟡 P7910 [CSP-J 2021] 插入排序

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

🔗 P7910 [CSP-J 2021] 插入排序

Problem Statement

題目簡述

給定長度為 $n$ 的陣列，支援兩種操作：

• 1 x v：把第 $x$ 個元素修改成 $v$
• 2 x：若對當前陣列執行題目給定的插入排序，詢問「原本第 $x$ 個元素」在排序完成後會落在第幾個位置

這裡的插入排序只會在 a[j] < a[j-1] 時交換，因此相同值不會互換順序；也就是說，相同值時要按照原下標決定先後。
類型 1 會真正修改陣列並影響後續操作，類型 2 僅查詢、不保留排序結果。

Constraints

約束條件

• $1 \le n \le 8000$
• $1 \le Q \le 2\times 10^5$
• $1 \le a_i, v \le 10^9$
• $1 \le x \le n$
• 所有操作中，至多只有 $5000$ 次屬於類型 1

---

思路：把插入排序轉成「穩定排序後的排名」

1. 核心觀察：題目的插入排序其實就是穩定排序

題目中的交換條件是：

if (a[j] < a[j-1]) swap(a[j], a[j-1]);

注意這裡是嚴格小於 <，不是 <=。

所以如果兩個元素值一樣，它們永遠不會互換相對順序。這正是穩定排序的特徵，因此整個插入排序做完後的結果，其實等價於：

• 先按照值由小到大排序
• 值相同時，按照原本下標由小到大排序

換句話說，每個元素都可以視為一個二元組：

$$(a_i, i)$$

而查詢 2 x 要問的，就是二元組 $(a_x, x)$ 在所有二元組排序後的名次。

關鍵等價

「插入排序後的位置」其實就是 (值, 原下標) 做字典序排序後的位置。
這句話一成立，整題就從「模擬插入排序過程」變成「維護穩定排序後的排名」。

2. 查詢公式：排名由兩部分組成

對固定的下標 $x$，所有值比它小的元素，一定排在它前面；值和它相同但原下標比較小的那些元素也會排在它前面，因此它的最終排名就是：

$$1 + \#\{i \mid a_i < a_x\} + \#\{i \mid i < x,\ a_i = a_x\}$$

兩種做法其實都在維護這個排名，只是維護方式不同：

• 方法一直接維護整個排序後序列
• 方法二分開維護「比它小的有多少個」與「同值且在左邊的有多少個」

方法一：暴力維護排序後序列

由於題目保證類型 1 的修改次數最多只有 $5000$，其實可以接受每次修改花 $\mathcal{O}(n)$ 去調整位置。

先建立一個排序後的陣列：

$$B = \text{sorted}((a_i, i))$$

再用 $pos[idx]$ 記錄「原本第 $idx$ 個元素現在在 $B$ 的哪個位置」。

這樣一來：

• 查詢 2 x 時，答案就是 $pos[x] + 1$ (因為排名是從 $1$ 開始算的)
• 修改 1 x v 時，只需要把 $(a_x, x)$ 改成 $(v, x)$，再把它移到正確位置

為什麼修改時只要往單一方向移動？

原本在 B 裡，除了第 x 個元素之外，其餘元素的相對順序完全不變。

因此當 (a_x, x) 改成 (v, x) 之後，它只可能：

• 如果 v > a_x：變大，往右移
• 如果 v < a_x：變小，往左移

不需要整段重排，只要像氣泡排序那樣和相鄰元素交換，直到恢復有序即可。每交換一次時，同步更新 pos 陣列。

為什麼可以比較 tuple？

Python 的 tuple 會先比第一項，再比第二項，所以 (值, 原下標) 的比較方式，剛好就是題目所需的穩定排序順序。

複雜度分析

• 時間複雜度：$\mathcal{O}(n \log n + q + kn)$，其中 $k$ 是類型 1 的次數，且 $k \le 5000$。初始化排序要 $\mathcal{O}(n \log n)$，每次查詢 2 為 $\mathcal{O}(1)$，每次修改最壞往左或往右移動整段，為 $\mathcal{O}(n)$。
• 空間複雜度：$\mathcal{O}(n)$。

方法二：BIT + SortedList 分開維護排名兩部分

若想直接用查詢公式算排名，可以把答案拆成兩項：

$$\text{rank}(x)=1+\underbrace{\#\{i \mid a_i<a_x\}}_{\text{值比較小的個數}}+\underbrace{\#\{i \mid i<x,\ a_i=a_x\}}_{\text{同值且原下標較小的個數}}$$

1. 第一項：比它小的值有多少個

這就是一個「動態維護 multiset 中各值出現次數」的問題。

因為 $a_i, v$ 最多到 $10^9$，先把：

• 初始陣列中的所有值
• 所有修改操作可能出現的新值

一起離散化。之後用 Fenwick Tree 維護每個值目前出現了幾次。

若第 $x$ 個元素目前值為 $A[x]$，那麼 bit.preSum(mp[A[x]] - 1) 就是所有比它小的值的總個數。

2. 第二項：同值且在左邊的有多少個

對每個值 $v$，維護一個有序集合 $pos[v]$，裡面存所有滿足 A[i] = v 的下標。

那麼對查詢 $x$ 而言，pos[A[x]].bisect_left(x) 就等於在所有值等於 $A[x]$ 的位置中，有多少個下標嚴格小於 $x$。

這正好就是穩定排序中「同值時排在它前面的元素數量」。

3. 修改如何維護？

若執行 1 x v：

1. 從 BIT 中把舊值 $A[x]$ 的出現次數減一
2. 把新值 $v$ 的出現次數加一
3. 從 $pos[A[x]]$ 刪除 $x$
4. 把 $x$ 加入 $pos[v]$
5. 更新 $A[x] = v$

如此每次操作都只會動到一個位置，且 BIT 和 SortedList 的操作都是對數級別，因此能在對數時間內完成。

這個做法在算什麼？

它不是在模擬插入排序，而是在直接求 (A[x], x) 的字典序排名。
這比維護整段排序結果更抽象，但複雜度也更漂亮。

複雜度分析

• 時間複雜度：$\mathcal{O}((n+q)\log(n+q))$。
  • 離散化需要保留所有可能出現的值，總共 $n$ 個初始值和最多 $q$ 個修改值，因此是 $O(n + q)$ 的規模；排序離散化的值要 $O((n+q)\log(n+q))$。
  • 因此 BIT 的大小也是 $O(n+q)$，在初始化 $n$ 個值時需要 $O(n \log(n+q))$，每次修改和查詢也是 $O(\log(n+q))$，總共需要 $O(q \log(n+q))$。
  • pos[v] 的插入、刪除和 bisect_left 都是 $log(n)$ 級別的操作，因為每個值最多出現 $n$ 次。
• 空間複雜度：$\mathcal{O}(n+q)$。需要儲存所有可能出現的值做離散化，外加 BIT 與各值對應的位置集合。

---

Code

方法一：暴力維護排序後序列

def solve():
    n, q = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == n

    B = [(x, idx) for idx, x in enumerate(A)]
    B.sort()
    pos = [-1] * n
    for i, (_, idx) in enumerate(B):
        pos[idx] = i

    def swap(i, j):
        pos[B[i][1]], pos[B[j][1]] = pos[B[j][1]], pos[B[i][1]]
        B[i], B[j] = B[j], B[i]

    for _ in range(q):
        op, *args = map(int, input().split())
        if op == 1:
            idx, v = args[0] - 1, args[1]
            B[pos[idx]] = (v, idx)
            if v > A[idx]:
                i = pos[idx]
                while i + 1 < n and B[i + 1] < B[i]:
                    swap(i, i + 1)
                    i += 1
            else:
                i = pos[idx]
                while i - 1 >= 0 and B[i - 1] > B[i]:
                    swap(i, i - 1)
                    i -= 1
            A[idx] = v
        else:
            idx = args[0] - 1
            print(pos[idx] + 1)  # 1-indexed


if __name__ == "__main__":
    solve()

方法二：BIT + SortedList 分開維護排名兩部分

Warning

這份 Python 程式碼使用 sortedcontainers.SortedList 方便表達想法，但 Luogu 不支援這個套件。
若要正式提交，需要自行實作可支援插入、刪除、排名查詢的有序結構，可以見我在 vjudge 上的 提交紀錄 (需登入)。

from collections import defaultdict
from sortedcontainers import SortedList

class BIT:  # PURQ, 1-based
    __slots__ = ["tree"]

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

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

    def preSum(self, k: int) -> int:  # 求 nums[:k+1] 之和
        res = 0
        while k > 0:
            res += self.tree[k]
            k -= k & -k
        return res

    def query(self, l: int, r: int) -> int:  # 求 nums[l:r+1] 之和
        if l > r:
            return 0
        return self.preSum(r) - self.preSum(l - 1)


def solve():
    n, q = map(int, input().split())
    A = list(map(int, input().split()))
    queries = [tuple(map(int, input().split())) for _ in range(q)]
    assert len(A) == n

    # 離散化
    Xs = set(A) | set(query[2] for query in queries if query[0] == 1)
    m = len(Xs)
    Xs = sorted(Xs)
    mp = {x: i for i, x in enumerate(Xs, start=1)}

    bit = BIT(m + 1)
    for x in A:
        bit.add(mp[x], 1)

    pos = defaultdict(SortedList)
    for i, x in enumerate(A):
        pos[x].add(i)

    for query in queries:
        op, *args = query
        if op == 1:
            idx, v = args[0] - 1, args[1]
            bit.add(mp[A[idx]], -1)
            bit.add(mp[v], 1)
            pos[A[idx]].remove(idx)
            pos[v].add(idx)
            A[idx] = v
        else:
            idx = args[0] - 1
            print(bit.preSum(mp[A[idx]] - 1) + pos[A[idx]].bisect_left(idx) + 1)

if __name__ == "__main__":
    solve()