HDOJ 5338 ZZX and Permutations：線段樹+樹狀數組構造字典序最大排列

問題重述

給定去掉括號後的排列分解序列，需恢復原排列並使其字典序最大。排列可分解為不相交循環，去括號後順序不唯一，需選最優方案。

貪心策略與數據結構

從 1 到 n 貪心決定每個數字的「去向」：

1. 右鄰交換：若右邊第一個數未被佔用，可與之交換。線段樹將該位置置 0 標記已用。
2. 左跳轉：跳至左側某數，意味著左側為左括號、當前為右括號。線段樹查詢區間最大值，樹狀數組二分確定左邊界（括號不重疊）。右括號位置在樹狀數組 +1 標記。
3. 自循環：如 2 1 3 可分解為 (2)(1 3)，字典序更大，允許數字指向自己。

關鍵數據結構操作

• 線段樹：維護區間最大值，支持單點置 0（標記已用）與區間查詢最大值。push_down 傳遞懶標記。
• 樹狀數組：維護括號完成標記，add 標記右括號，get_left 二分查找最左可用左括號位置。

核心邏輯片段

for (int i = 1; i <= n; ++i) {
    int left = get_left(wz[i]) + 1;
    int right = wz[i] + 1;
    int self = i;
    // 三種選擇取字典序最大者
    if (right > self) {
        ans[i] = right; used[wz[right]] = true; update(wz[right], wz[right], 1, n, 1);
    } else if (left > self) {
        ans[i] = left;
        // 連接循環：標記中間區間
        for (int j = wz[left]; j < wz[i]; ++j) ...
    } else {
        ans[i] = self; // 自循環
    }
}

複雜度與總結

時間 O(n log n)，空間 O(n)。題目巧妙結合線段樹區間最大值查詢與樹狀數組二分邊界，將排列循環分解轉化為區間操作問題，是數據結構綜合應用的優秀範例。