莫隊時間分塊複雜度到底怎麼算QAQ?

01-08

ACM 莫隊分塊

顯然最多有sqrt（m）個塊、對於塊內每個詢問來說、右端點每次變換最多sqrt（m）次，所有詢問一共n個，所以最多n*sqrt（m）次、左端點的話、因為最多sqrt（m）個塊，所以構造每個塊第一個詢問的左端點最多每次走m步、共msqrt（m）次，由於n往往和m相等，所以莫隊複雜度是更號級別的，排序的log相比更號太小了所以忽略

$O(n^{1.5})$ 次修改和 $O(n)$ 次查詢。

注意這兩個需求並不平衡，所以在搭配數據結構時常使用分塊而不是線段樹。

震驚：99%的人不知道莫隊的真正複雜度！

O( nsqrt( m ) )

分塊的複雜度則是O( nsqrt( n ) ) + O( nsqrt( m ) )

//我們假設你要預處理塊間的鬼玩意

其實n=1e5,m=1e6的題莫隊是可以隨便跑的

參見Problem 4940. -- [Ynoi2016]這是我自己的發明

只不過要調分塊大小為n / sqrt( m )級別

艾教說得挺清楚的了,補充一點,莫隊分塊時間複雜度還取決於左右指針每一次移動的時間複雜度,如果移動一下指針需要logn複雜度的話還得乘上(逃

-----------------------------------------分割線------------------------------------------------------

詳細些，以例題小Ｚ的襪子來說，指針左右移動都是O(1)的複雜度,長度為n, q個詢問,我們將長度為n的區間分成sqrt(n)的塊,然後將詢問排序,按左端點的塊的序號為第一關鍵字，右端點為第二關鍵字排好序以後，我們將左指針和右指針分開來看，左指針對於q個詢問，每次最多移動一整塊的長度也就是sqrt(n)，所以左指針總移動次數不會超過q*sqrt(n), 對於右指針，由於對於每個塊內詢問是按右端點為第二關鍵字排序的，因此對於一個塊，右指針最多O(n)的從最左邊掃到最右邊，一共有sqrt(n)個塊，所以考慮右指針是n*sqrt(n)，所以總時間複雜度是O(q*sqrt(n) + n*sqrt(n))

設轉移時間為 $O(F)$ ，對 $x$ 進行分塊。

塊大小為 $Theta(sqrt{N})$ 。一塊內和兩塊間的 $x$ 方向移動次數都是 $O(N)$ ，共有 $Theta(sqrt{N})$ 塊，所以 $x$ 方向移動次數共為 $O(N cdot sqrt{N})$ 。兩次查詢之間 $y$ 方向移動次數為 $O(sqrt N)$ ，共有 $Q$ 次查詢，所以 $y$ 方向移動次數為 $O(sqrt N cdot Q)$ 。總複雜度為 $O((N + Q) sqrt N cdot F)$ 。
塊大小為 $Theta(frac N {sqrt Q})$ 。一塊內和兩塊間的 $x$ 方向移動次數都是 $O(N)$ ，共有 $Theta(sqrt Q)$ 塊，所以 $x$ 方向移動次數共為 $O(N cdot sqrt{Q})$ 。兩次查詢之間 $y$ 方向移動次數為 $O(frac N {sqrt Q})$ ，共有 $Q$ 次查詢，所以 $y$ 方向移動次數為 $O(N cdot sqrt Q)$ 。總複雜度為 $O(N sqrt Q cdot F)$ 。

修改於09-28，09-15可能是廢話寫太多了。