作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 主席树？
时间Thu Feb 5 13:46:44 2015
1F：→ FRAXIS: 可不可以简单介绍一下莫队算法的功用啊？ 02/05 01:26
现在有许多个区间查询 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)
我们现在
替 Q 中所有查询，安排适当计算顺序，让总时间最少。
查询视为座标，即 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
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1423115208.A.6A7.html
※ 编辑: DJWS (111.250.78.113), 02/05/2015 13:56:52
※ 编辑: DJWS (111.250.78.113), 02/05/2015 13:57:31
2F：推 dreamoon: 总觉得这种食後要贴出那个Let me google that for you.. 02/05 16:13
3F：推 FRAXIS: 挺有趣的技巧 我研究看看 02/05 23:17
4F：推 FRAXIS: 我有点搞不懂 那是不是把所有ai, bi 排序 一个一个作就好? 02/05 23:20
6F：→ DJWS: 按照XY座标排序之後顺序 总距离通常较长 02/06 19:32
7F：→ DJWS: 然後图中的直线改成阶梯状就是 rectangular distance 02/06 19:33
8F：推 FRAXIS: 了解了 感谢 02/06 22:17
9F：推 FRAXIS: 但是不能把整个空间分块吗？ 然後每一区块选一个中心 02/06 22:38
10F：→ FRAXIS: 这样就可以先preprocess 来 speed-up查询 02/06 22:38
11F：推 FRAXIS: 我上网看了一下 大概了解是在干嘛了.. 02/07 04:20
13F：→ DJWS: 这个算法跟区间查询其实没有直接关系 02/07 12:16
14F：→ DJWS: 这个技巧其实还可以套用到 dynamic programming 状态转移 02/07 12:17
15F：→ DJWS: 然後你讲的也是一个好方法 应该就是ALT Algorithm 02/07 12:20
17F：→ FRAXIS: 这技巧应该是因为实作比较容易 02/07 23:11