POJ 3481 Double Queue：STL map 實現雙端隊列

題目要求

維護一個集合，支持三種操作：插入元素、刪除最大元素、刪除最小元素。需輸出被刪除元素的關聯值。

解法：利用 map 有序特性

C++ STL `map` 以鍵值自動排序（默認按 key 升序）。將輸入的數值作為 key，關聯值作為 value 存入 map。插入 O(log n)，刪除最大/最小分別操作 `end()` 和 `begin()` 迭代器，同樣 O(log n)。

核心代碼邏輯

if (op == 1) { map[key] = val; ++sz; }
else if (op == 2) { // 刪除最大
    if (sz == 0) puts("0");
    else { auto it = prev(map.end()); printf("%d\n", it->second); map.erase(it); --sz; }
}
else if (op == 3) { // 刪除最小
    if (sz == 0) puts("0");
    else { auto it = map.begin(); printf("%d\n", it->second); map.erase(it); --sz; }
}

優缺點分析

• 優點：代碼極簡，利用標準庫紅黑樹實現，無需手寫平衡樹。
• 缺點：常數因子較大，若數據量極大（如 10^6 操作）可能需優化為自寫堆或 Treap。

適用場景

適合數據量中等、操作單純的雙端優先隊列問題，快速編寫、不易出錯。