PKU3481-DoubleQueue

題目頁：http://poj.org/problem?id=3481
每個用戶有識別號K以及優先度P
有很多用戶要登入銀行系統等待被處理
給一段操作序列，可能有
1.加入某用戶(K,P)
2.服務優先度最高的用戶
3.服務優先度最低的用戶
對每個2、3操作輸出被處理到的用戶識別號
如果沒有用戶等待被處理，就輸出0

程式碼：http://codepad.org/sYVUHCQG

跟很久以前寫的TIOJ1415非常像(上次AC是2010-1-1耶好懷念)
就是建一個佇列還是動態樹啥的
讓它可以支持隨時拔走最大值or最小值的操作
當年是開hash隨便亂爆XD
最近知道可以用map的begin()、end()秒殺...
(也就是說任何二叉搜索樹都適用，AVL、紅黑甚至隨機旋轉的Treap)

因為正在學Splay伸展樹
所以就試看看用Splay來作(順便熟悉刪除操作)
重點是刪除操作卡超久的...囧
途中本來是用root記錄現在誰是根結點
後來debug到有點煩了才臨時換成虛擬root(就是用L[0]來記錄樹根、0是假樹根)

1.得意的地方：函式rotate、splay
構造的時候經過多番考慮
決定還是不維護p[] (該節點的父結點)
因為這樣旋轉的時候會發瘋...
所以splay函式一開始的stack就相當於直接往下搜到x點並記錄路徑
論空間論時間總地來說反正都一樣
於是這兩個函式就異常的簡潔：輕鬆的提跟、輕鬆的旋轉

2.難點：函式delwos (delete without splay，詳見3)
花最多時間修復的地方，直到參考了這篇文章
就總結一下他說的
考慮被刪除結點的三種情況：
A.沒有兒子：直接砍掉、沒甚麼好說
B.僅有一個兒子：讓那個兒子代替原本的位子
C.有兩個兒子最麻煩
大致是找出前趨或後繼(也就是索引值"最接近"該節點的點)
然後用那個點來取代原本的位置，並且作細節的維護

3.仍然不懂的地方：伸展操作的複雜度
國家集訓隊2004年楊思雨論文提到，每次插入或刪除都要伸展
不過插入如果是連續由小到大的數字還是會變成最不平衡的那種樹阿？
刪除部分以本題來說更是這樣，每次都把最大最小變成根，應該更慘？

所以我自作主張把插入改成隨機splay一個點
刪除就不作splay
測試這題之後得到的秒數是這樣的
插入隨機splay、刪除不作splay：563ms
插入隨機splay、刪除正常splay：563ms
插入正常splay、刪除正常splay：594ms

頗不尋常的結果，或許測資分佈以隨機插入為主？又或許我真的不懂QQ

接下來開始挑戰splay維護序列的應用問題