BZOJ 2141：排隊 - 樹套樹 (線段樹套平衡樹) 維護逆序對

問題描述

給定長度 n 的排列，支持交換兩位置元素，每次交換後輸出當前逆序對總數。n, q ≤ 20000。

數據結構：線段樹套 Treap (Tree + Heap)

• 外層線段樹按 位置 分塊，每個節點維護一個 Treap（平衡 BST），存儲該區間內的 值。
• 查詢區間 [l, r] 中 小於/大於給定值 的個數：分解為 O(log n) 個線段樹節點，在各自 Treap 中查詢 O(log n)，總 O(log^2 n)。
• 單點修改（交換兩位置值）：在 O(log n) 個線段樹節點中各刪除舊值、插入新值，各 O(log n)，總 O(log^2 n)。

逆序對維護邏輯

交換位置 x < y，值 a = A[x], b = A[y]。逆序對變化：

• 中間區間 (x, y)：原有 a 與中間元素的逆序關係消失，新增 b 的；同理 b 與中間的關係互換。
• 直接計算：Δ = (中間 < a 的個數) - (中間 > a 的個數) + (中間 > b 的個數) - (中間 < b 的個數)，再加上 a,b 自身相對順序變化（若 a < b 則 +1，若 a > b 則 -1）。

代碼框架

struct Treap {
    int val, pri, sz, cnt;
    Treap *l, *r;
    // insert, erase, count_less, count_greater ...
};

Treap* seg[4*MAXN];

void seg_insert(int node, int l, int r, int pos, int val) {
    treap_insert(seg[node], val);
    if (l == r) return;
    int mid = (l+r)/2;
    if (pos <= mid) seg_insert(node*2, l, mid, pos, val);
    else seg_insert(node*2+1, mid+1, r, pos, val);
}

int seg_query_less(int node, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) return treap_count_less(seg[node], val);
    int mid = (l+r)/2, res = 0;
    if (ql <= mid) res += seg_query_less(node*2, l, mid, ql, qr, val);
    if (qr > mid) res += seg_query_less(node*2+1, mid+1, r, ql, qr, val);
    return res;
}

複雜度

• 初始構建：O(n log^2 n)。
• 每次交換：O(log^2 n) 查詢 + O(log^2 n) 修改 = O(log^2 n)。
• 總體 O((n+q) log^2 n)，n=20000 可過。

總結

「樹套樹」是二維離線/在線查詢的通用結構。本題將「位置」作為第一維線段樹，「值」作為第二維 Treap，高效支持區間值排名查詢與單點更新，從而動態維護逆序對數。