HDU 4441 Queue Sequence：Splay Tree + Segment Tree 維護雙端隊列

題目大意

維護一個初始為空的序列，支持三種操作：

1. Insert：找最小未用正整數 i，插入位置 pos；同時插入 -i 到第 k+1 個負數之前（k 為 +i 前的正數個數），保持正負數相對順序。
2. Remove：刪除 i 和 -i。
3. Query：查詢 i 和 -i 之間元素和。

m ≤ 200000 操作。

核心數據結構

• Splay Tree：維護序列順序，支持按秩插入/刪除/區間求和。每節點記錄：
  • val：值（正/負）
  • sum：子樹值和
  • z：子樹正數個數
  • f：子樹負數個數
• Segment Tree：維護「最小未用正整數」。葉子節點 1..m，值 1 表示未用，0 表示已用。區間最小值即答案。

關鍵操作實現

Insert(pos)

1. num = seg.query_min() 獲取最小可用正整數。
2. Splay 插入 +num 到位置 pos+1（Splay 以 1-based 索引，含哨兵節點）。記錄節點指針 pos1[num]。
3. Splay 根統計 z[root] 即 +num 前的正數個數 k。
4. 若總負數個數 f[root] ≤ k，則 -num 插到序列末尾（size-1 位置）。
5. 否則用 kth(root, k) 找第 k+1 個負數位置，插在其前。記錄 pos2[num]。
6. Segment Tree 更新 num 為已用（置 INF）。

Remove(num)

1. Splay pos1[num] 到根，刪除該節點（雙旋刪除哨兵間節點）。
2. 同理刪除 pos2[num]。
3. Segment Tree 更新 num 為可用（置 num）。

Query(num)

1. Splay pos1[num] 到根，pos2[num] 到根的右子樹。
2. 區間和即 keyTree->sum（中間子樹）。

複雜度

• Splay 操作均攤 O(log n)。
• Segment Tree O(log m)。
• 總體 O(m log m)，通過 m=200000。

代碼結構要點

// Splay 節點
int ch[MAXN][2], pre[MAXN], siz[MAXN], val[MAXN];
long long sum[MAXN];
int z[MAXN], f[MAXN]; // 正/負計數

// Segment Tree
int seg[MAXN<<2];
void build(int o, int l, int r) { ... }
void update(int o, int l, int r, int pos, int val) { ... }
int query_min() { return seg[1]; } // 根存最小可用數

// Splay 基礎操作：rotate, splay, rotateTo(k, goal)
// kth(x, n): 找第 n 個負數位置
// insert(pos, v): 旋轉到位置插入
// remove(num): 旋轉到節點刪除

完整代碼見原文，包含調試用 Treaval 遍歷輸出。

總結

本題綜合考察 Splay Tree 維護序列結構 + Segment Tree 維護最小可用數。關鍵難點：

1. 正負數插入位置的相對順序邏輯（kth 找負數排名）。
2. Splay 中哨兵節點設計（頭尾各一哨兵，簡化邊界）。
3. 區間求和利用 Splay 的「伸展到區間邊界」技巧。

是數據結構綜合應用的優秀練習題。