關于三維莫隊問題的一些思考和探究

手動博客搬家: 本文發表于20180919 15:41:25, 原地址https://blog.csdn.net/suncongbo/article/details/82771387

背景介紹

首先，我是一名菜雞。
前幾天在做bzoj 5283時，經過轉化后需要處理這樣一個二元函數
\(S(x,y)=\sum^{x}_{i=1} C^i_y\)
其中有\(Q\)組詢問，\(x\le y\le 2.5\times 10^5, Q\le 2.5\times 10^5\).
做法是：我們發現這個函數的重要性質是，假如已知\(S(x,y)\), 那么我們可以在\(O(1)\)的時間內轉移得到\(S(x+1,y), S(x-1,y), S(x,y+1), S(x,y-1)\).
于是，我們依照莫隊的思想，將所有詢問離線下來。
對于詢問\(S(x_1,y_1), S(x_2,y_2)\) 按如下的規則進行比較排序：
首先比較\(\frac{x_1}{\sqrt n}\)與\(\frac{x_2}{\sqrt n}\)的值，小的在前。
如果這兩個值相同的話，再比較\(y_1\)與\(y_2\).
從一個詢問跳到另一個詢問時，我們直接暴力一個一個地把左端點從\(x_1\)移到\(x_2\), 右端點從\(y_1\)移至\(y_2\).
這樣對所有詢問排序后 ，我們計算左右端點的移動總距離。假設\(Q,n\)同階。
左端點移動距離\(T_1\): 對于每個大小為\(\sqrt n\)的塊，左端點一定要在塊內移動。每次移動的距離不超過\(\sqrt n\), 每個塊內移動的總次數不超過\(n\) (\(n\)個詢問), 總移動的距離不超過\(n\sqrt n\). 這是塊內的情況，而左端點在塊與塊之間移動時，每次移動的距離不超過\(2\sqrt n\), 但是由于只有\(\sqrt n\)個塊，因此總移動次數不超過\(\sqrt n\), 總距離\(O(n)\). 綜上，左端點移動總距離\(O(n\sqrt n)\).
而右端點呢？更簡單：對于左端點在同一個大小為\(\sqrt n\)的塊內的詢問，右端點是單調右移的，移動總距離不超過\(n\), 又因為有\(\sqrt n\)個塊，因此總距離\(O(n\sqrt n)\).
綜上，左右端點移動的總距離為\(O(n\sqrt n)\), bzoj 5283這道題已經在\(O(n\sqrt n)\)的復雜度內解決，均攤每次詢問\(O(\sqrt n)\).（然而bzoj老爺機毒瘤卡常嗚嗚嗚...）

問題引入——三維莫隊

剛才，我們處理的是一個二元函數\(S(x,y)\), 具有重要的轉移性質。現在我們拓展這個問題，假設我們有一個三元函數\(f(x,y,z)\), 其可以在\(O(1)\)的時間內轉移到\(f(x-1,y,z), f(x+1,y,z), f(x,y-1,z), f(x,y+1,z), f(x,y,z-1), f(x,y,z+1)\)這六個值。有\(Q\)次詢問，每次詢問一個\(f(x,y,z)\)的值，\(x,y,z\le n\), 是否可以較快速地求出所有詢問的答案呢？
假設\(Q, n\le 4.5\times 10^4\).

個人的想法

仿照二維莫隊的思路，我們首先對詢問進行排序。
我們來形式化地推一發。
設我們的排序方式是第一關鍵字\(\frac{x}{n^a}\), 第二關鍵字\(\frac{y}{n^b}\), 第三關鍵字\(z\).
對于\(x\), 在每個塊內移動距離\(O(n^a)\), 總詢問數\(O(n)\), 總距離\(O(n^{1+a})\).
對于\(y\), 當\(x\)在同一大塊內時，\(y\)每次移動距離\(O(n^b)\), 共\(n\)個詢問，\(O(n^{1+b})\). 當\(x\)不在同一大塊內時，有\(O(n^{1-a})\)個大塊，每個大塊\(y\)要移動\(n\)的距離，因此\(O(n^{2-a})\). 綜上，\(y\)移動距離\(O(n^{\max(1+b,2-a)})\).
對于\(z\), 我們考慮\(x,y\)的塊總共會將\(n\)個詢問分成\(O(n^{1-a+1-b})\)類，對于每一類詢問，都要移動\(n\)的距離，因此\(z\)移動距離\(O(n^{3-a-b})\).
然后我們來最優化。首先，為了讓復雜度不至于達到\(O(n^2)\), \(3-a-b\)必須\(\lt 2\), \(a+b\gt 1\). 而對于\(y\)的\(\max(1+b,2-a)\), \(1+b\gt 2-a\)等價于\(a+b\gt 1\), 因此恒滿足，\(y\)的復雜度其實就是\(O(n^{1+b})\).
然后就簡單了……\(O(n^{1+a}), O(n^{1+b}), O(n^{3-a-b})\), 平衡一下，顯然\(a=b=n^\frac{2}{3}\)時取最優，\(O(n^\frac{5}{3})\), 單次均攤\(O(n^\frac{2}{3})\).

后記

重申，本人弱雞，剛剛從bzoj 5283這道題里得到的啟發，推了一發寫了此文，若有錯誤敬請大佬們指出，感激不盡。
關于三維莫隊問題，目前沒有任何一個人跟我討論過，純粹是我自己的一點想法，也沒有找其他人檢驗過（我好菜啊），也沒有專門看過此類課題的論文，因此文章內容很可能有錯誤之處。不過剛才推了這么一大串，最后的核心思想就是一個，通過排序平衡三個端點的移動距離。剛才的內容如果正確，還可以推廣到更高維的情況，但是更高維大概只有理論價值，實際上并不會比\(O(n^2)\)暴力快到哪里去。我相信，這個簡簡單單的問題早已被之前的大佬們解決，我只是發表一點自己的思考而已。如果哪位大佬在這個問題上有更優秀的做法，敬請指出，謝謝。

發表于 2019-01-22 19:45 suncongbo 閱讀(...) 評論(...) 編輯 收藏 刷新評論刷新頁面返回頂部 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的关于三维莫队问题的一些思考和探究的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。