→ FRAXIS: 用來計算 離線的區間 k 大查詢 03/10 20:24
我研究了一下，如果元素有 n 個，查詢有 m 個，當 m 至少為 n^0.5，
莫隊算法那空間複雜度應該會是 O((n+m) * n^0.5 * (狀態轉移cost) + 排序)
空間是 O(m+狀態表示)。
所以我猜主要的優勢是在好實作和省空間吧。
我嘗試了幾個題目（假設m = O(n)）
1. Range inversion counting: 求區間內的逆序對
2. Range sum of distinct elements: 區間內相異元素之和
3. Range second frequency moment: 求區間內元素出現次數的平方和
4. Range mode query: 求區間內的眾數
1 的 offline 查詢為 O(n^0.5 lg n)
online 查詢為 O(n^0.5) 空間 O(n^1.5)
或查詢為 O(n^0.5 lg n) 空間 O(n)
2, 3, 4 的 offline 查詢為 O(n^0.5)
4 的 online 查詢為 O(n^0.5) 空間 O(n)
2, 3 的 online 查詢為 O(n^0.5) 空間 O(n^1.5)
或查詢為 O(n^0.5 lg n) 空間 O(n)
不知道能不能做成 查詢為 O(n^0.5) 空間 O(n)
至於動態的話，就把 block 大小調小一點就可以了。
好像還有看到題目是 range distinct elements，找區間相異數字的個數，
這應該是O(lg n)可解的。
還有一些相關的問題，像是區間 majority，區間 minority，
區間前 k 大 (sorted/unsorted)，或是區間出現最多次的 k 個元素。
--
這技巧蠻有趣的，不知道還有沒有其他神奇的技巧呢？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1423324040.A.C3E.html
※ 編輯: FRAXIS (129.170.195.149), 02/09/2015 23:24:59