HDU 5338 ZZX 與排列：線段樹解法詳解

問題背景

ZZX 喜歡排列，並知道任何排列都可以分解為不相交的循環。例如排列 145632 可以分解為 (1)(35)(462)。移除所有括號後，分解序列可能是 135462、462135 等多種形式。給定移除括號後的分解序列（本身也是一個排列），要求恢復原始排列，並找出字典序最大的解。

核心思路

這是一個經典的線段樹應用題目。關鍵在於維護區間最大值，並結合貪心策略構建字典序最大的排列。算法流程如下：

1. 預處理：記錄每個數字的位置，並按數值排序
2. 使用線段樹維護區間最大值，支持單點更新（將已用位置標記為 -1）
3. 從大到小枚舉數字，嘗試將其放置在最優位置
4. 利用集合維護已確定的循環邊界

關鍵代碼片段

struct node { int l, r; int ma; } tree[N << 2];
void build(int l, int r, int id) {
    L(id) = l; R(id) = r;
    if (l == r) { M(id) = a[l]; return; }
    int mid = (l + r) >> 1;
    build(l, mid, ls); build(mid + 1, r, rs);
    Up(id);
}
int query(int l, int r, int id) {
    if (l == L(id) && R(id) == r) return M(id);
    int mid = (L(id) + R(id)) >> 1;
    if (r <= mid) return query(l, r, ls);
    else if (mid < l) return query(l, r, rs);
    else return max(query(l, mid, ls), query(mid + 1, r, rs));
}

複雜度分析

時間複雜度：O(n log n)，其中 n ≤ 10^5。空間複雜度：O(n)。

測試樣例

輸入：
2
6
1 4 5 6 3 2
2
1 2

輸出：
4 6 2 5 1 3
2 1