分析

• 小於 \(\sqrt{N}\)：通常是暴力
• 大於 \(\sqrt{N}\)：因為大於的數會有\(O(N)\)個，所以轉移或操作的複雜度平均要是\(O(\sqrt{N})\)以下。通常圍繞著\(\sqrt{N}\)跑。

例題

題目：非常多，到處都是

1. ABC 219G
2. LOJ 6089

例題

給定一個陣列\(A\)，支援以下操作：

1. 區間加值
2. 區間查詢

分塊先備條件

1. 大段維護，局部暴力
2. 局部暴力通常不成問題難在如何維護整塊的資訊
3. 除了維護單一塊內資訊，如何合併答案也很重要

慣用手法

1. 首先先把陣列分成若干塊，每塊大小為 \(B\)，不足的就讓它不足
2. (可選) 標記每一個位置是屬於哪一塊，通常 0-base 我們會使用 \(\frac{i}{B}\) 來作為塊編號(向下取整)
3. 對於一個區間 \([L,R]\)，最多會包含到兩個不完整的塊(左右)，局部處理這兩塊，剩下的用打tag的方式維護
4. 處理答案的合併

例題講解

1. 區間修改：不完整的塊一個一個修改，完整的塊打一個tag: 塊內元素*val
2. 區間查詢：同上，修改改成相加即可

複雜度

1. 不完整的塊一個一個修改：\(O(2B)=O(B)\)
2. 完整的塊打一個tag: \(O(N/B)\)

總複雜度：\(O(Q(B+N/B))\)，由算幾不等式可知取 \(B=\sqrt{N}\)最優，整體複雜度\(O(Q\sqrt N)\)

分塊可以做什麼

• 很多的區間問題，只要可以打tag維護通常都可
• 可以在塊內做二分搜，甚至可以塞資料結構
• 複雜度通常不好分析，但理論上他是好的
• 分塊本人就是一個資料結構，資料結構可以做的他都可以做 ex: DP 優化

值域分塊

值域分塊是一種資料結構

值域分塊

值域分塊是一種資料結構

跟值域線段樹很像，就是對值域進行分塊

每塊分別統整該塊的答案

題目?

他不太常出現，因為值域線段樹可以蓋掉大部分的CASE

但值域分塊還是有一些好用的地方：單點修很快

有些題目用是要用值域分塊才可以過的

回家作業

1. hzwer 的分塊 9 講 LOJ 6277~6285

又叫定期重構。適用於有修改也有查詢的題目。顧名思義將詢問進行分塊，當處理完整個塊所有的詢問時，將你的陣列一次加上那些修改操作。在塊內時暴力查詢不修改。

所以什麼是詢問分塊?

例題

給定一個陣列\(A\)，支援以下操作：

1. 區間加值
2. 區間查詢

例題講解

1. 每出現 \(\sqrt{Q}\) 次修改操作就把 \(A\) 加上那些修改重新算一遍。
2. 每次詢問最多只會有 \(\sqrt{Q}\) 的未處理修改，直接暴力計算那些修改對該詢問的影響。

回家作業

[MDCPP B053] 大電神說都沒人解他很難過QQ

品種

• 普通莫隊算法
• 帶修改莫隊
• 回滾莫隊
• 樹上莫隊
• 莫隊搭配bitset(?)

使用時機

可以離線做 當你有區間 \([L,R]\) 的答案時，可以快速算出區間 \([L,R-1],[L,R+1],[L-1,R],[L+1,R]\) 的答案

莫隊算法使用

1. 把序列分塊，塊大小 \(B\)
2. 把詢問區間按照以下規則排序：左界按所在的塊編號排序，右界按自己的編號排序。
3. 用兩個指針l,r每次一格一格移動指針到下一個詢問(先移右指針再移左指針)，過程中同時維護答案

複雜度分析

1. 排序 \(O(NlogN)\)
2. 當左界都在同一塊右界只會一直往右邊嚕。所以右界移動的格子數不超過 \(O(N)\)，而這種Case最多只會有 \(O(N/B)\) 種=>\(O(\frac{N^2}{B})\)
3. 左界都在同一塊內移動，所以一次最多移\(O(B)\)個位置，總共最多移\(O(Q)\)次整體複雜度\(O(QB)\)
4. \(O(NlogN+\frac{N^2}{B}+QB)\) 取\(B=\frac{N}{\sqrt{Q}}\)

1. 區間眾數
2. 區間MEX \(O(N\sqrt{N})\) Hint: 6I6r6ZqKKyAi5YC85Z+f5YiG5aGKIiDntq3orbfmlbTloYros4foqIo= 請用base64解碼 解碼器
3. 非常多題目

帶修改莫隊

可以帶修改的莫隊，我不會。大概是把時間這維加進去一起排序，然後做一些壞壞的事情。

時間複雜度：\(O(N^{5/3})\)，coding 複雜度：O(玄學)

回滾莫隊

可以回滾的莫隊。

回滾莫隊

可以回滾的莫隊。

當你發現你只會作加法(減法)的時候就可以考慮

回滾莫隊

可以回滾的莫隊。

當你發現你只會作加法(減法)的時候就可以考慮

所以回滾是什麼？

名詞解釋

• 加法：把某些東西加進答案
• 減法：把某些東西從答案扣掉
• 回滾：英文叫做 rollback，就是回到之前的某一個狀態

作法

1. 一樣先做莫隊，用下面的方法改一下
2. 右界：如果左界在同一塊的話右界會遞增，所以右界只會有加法
3. 左界：因為左界永遠都在同一塊，所以不妨每一次都暴力算那一塊的答案，算完之後直接退回就好

題目

1. 區間MAX
2. CF EDU DSU PART3 P2
3. 區間MEX
4. JOISC 2014 D1 某一題

樹上莫隊

在樹上做莫隊。但你要先會樹上分塊，請左轉選訓大電神。

假樹上莫隊

把樹壓平之後就變成序列問題了，直接莫隊

莫隊+bitset(?)

在做莫隊的時候轉移有時候可以套資料結構，就用bitset當資料結構就好了

莫隊+bitset(?)

在做莫隊的時候轉移有時候可以套資料結構，就用bitset當資料結構就好了

我也沒打過，請右轉OI WIKI