---

現在有許多個區間查詢 Q = { [a1,b1] , [a2,b2] , ... , [ak,bk] }
預計其查詢結果是  r[a1,b1] ... r[ak,bk]

假設問題具備此性質：
已知 r[a,b] ，可以快速求得邊界差一的結果如 r[a-1,b] r[a+1,b] r[a,b-1] r[a,b+1]
令計算時間為 O(f(n))

那麼，已知 r[ai,bi] 推得 r[aj,bj] 的時間就是 O((|ai-aj| + |bi-bj|) * f(n))
即 rectangular distance (L1)

查詢視為座標，即 minimum spanning tree with rectangular distance O(k log k)
找到樹之後，跑個DFS或BFS，就得到最佳的計算順序。

(理論上 steiner tree 效果更好，不過它是 NP-hard ...)

我理解的莫隊算法是這樣。
至於為什麼莫隊算法宣稱 O(n^1.5) ，我還沒搞清楚...

--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.78.113
※ 文章代碼(AID): #1KqmF8Qd (Prob_Solve)
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1423115208.A.6A7.html