---

我研究了一下，如果元素有 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
※ 文章代碼(AID): #1KrZE8m- (Prob_Solve)
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1423324040.A.C3E.html