HDU 3436 Queue：Splay 树離散化區間維護詳解

本題要求維護一個 1..N 的隊列，支持三種操作：top x（將編號 x 移至隊首）、query x（詢問編號 x 當前位置）、rank x（詢問第 x 位置的編號）。N、M 均達 10^5 級，需 O(log N) 單次操作。關鍵難點在於離散化區間，將未被 top/query 直接操作的大段連續區間壓縮為單一節點，配合 Splay 树的 size 域實現順序統計。

核心思想：離散化 + Splay 區間節點

1. 收集所有 top 和 query 涉及的編號，加上 N，排序去重 → 關鍵點集合。
2. 相鄰關鍵點之間的連續區間（如 2~6）整體作為一個 Splay 節點，節點的 val/size 存儲區間長度。
3. 關鍵點本身也各自佔一個長度為 1 的節點。
4. 初始按順序構建平衡 Splay 树（中序遍歷即原序列）。

操作實現

Top x（移至隊首）

• 二分查找 x 所在區間節點 y。
• Splay(y, 0) 將 y 旋至根。
• remove() 刪除根節點（y 所在區間/關鍵點）。
• insert(root, k, 0) 將 y 重新插入為最左節點（隊首）。
• Splay(y, 0) 更新根。

Query x（詢問位置）

• 二分定位 x 所在節點 y，Splay(y, 0)。
• 答案 = size[左子樹] + 1（若 x 是區間內部點，需加上區間內偏移，代碼中通過區間節點長度處理）。

Rank k（詢問第 k 位編號）

• 從根遞歸下降：設左子樹大小 = L，當前節點長度 = V。
• 若 k <= L 進左子樹；k <= L+V 答案在當前區間內，返回 區間起始 + (k-L-1)；否則進右子樹找 k-L-V。

關鍵代碼片段

// 離散化構建區間
sort(a+1, a+1+top);
high = unique(a+1, a+1+top) - a - 1;
a[0] = 0;
for (int i=1; i<=high; i++) {
    if (a[i] - a[i-1] > 1) { // 中間連續區間
        gap[cnt].s = a[i-1]+1; gap[cnt].e = a[i]-1;
        gap[cnt].v = gap[cnt].e - gap[cnt].s + 1; cnt++;
    }
    // 關鍵點自身
    gap[cnt].s = gap[cnt].e = a[i];
    gap[cnt].v = 1; cnt++;
}
high = cnt - 1;

// Splay 節點 size 維護
void pushup(int x) { siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + val[x]; }

// Rank 遞歸查詢
int rank(int r, int k) {
    int t = siz[ch[r][0]];
    if (k <= t) return rank(ch[r][0], k);
    else if (k <= t + val[r]) return gap[key[r]].s + (k - t) - 1;
    else return rank(ch[r][1], k - t - val[r]);
}

複雜度分析

• 離散化：O(M log M)
• Splay 構建：O(K) (K = 離散後節點數 ≤ 2M+1)
• 單次操作：O(log K) 攤還
• 總體：O((M+K) log K) 滿足 10^5 規模

總結

本題展示了離散化思想在動態序列維護中的威力：將大量連續不變的區間壓縮為單一節點，配合 Splay 树的序列操作能力（分裂、合併、順序統計），以極小的節點數解決大規模問題。這是數據結構題中「區間離散化 + 平衡樹」的經典套路，值得反覆琢磨。