[筆記]淺談分塊
0 前言
分塊真的是一個很好的思想和資料結構，它是一種優雅的暴力，
——LYM
1 分塊入門
一般來說，分塊解決的是在序列上的操作問題，在某種情況下，它可以運用一些簡單的操作來解決一些線段樹\樹狀陣列\樹套樹較為惡心的題目，
用一道例題來引入吧，
數列分塊入門 4
就是要設計一個支持區間加、區間求和查詢的題目，
考慮（線段樹）分塊，
先來想想最暴力的做法，查詢、修改都是 \(O(n)\) ，整體是 \(O(nm)\) ，顯然會炸，
不妨先把序列分成 \(\sqrt n\) 塊（實際上會多一點或少一點，但這不影響），每個塊的長度為 \(\sqrt {n}\)，
\[\underbrace{a_1,a_2,\cdots,a_{\sqrt{n}}}_{\text{第1個塊}},\underbrace{a_{\sqrt{n}+1},a_{\sqrt{n}+2},\cdots,a_{2\cdot \sqrt{n}}}_{\text{第2個塊}},\cdots,\underbrace{a_{(\sqrt{n}-1) \cdot \sqrt{n}+1},a_{(\sqrt{n}-1) \cdot \sqrt{n}+2},\cdots,a_{n}}_{\text{第} \sqrt{n} \text{個塊}} \]最后一個塊的長度可能不是 \(\sqrt{n}\) ，塊的個數也有可能會變動，但先不管，
設 \(b_1,b_2,\cdots,b_{\sqrt{n}}\) 為每一個塊要統一加上的數；\(s_1,s_2,\cdots,s_{\sqrt{n}}\) 為每個塊的實際的和 ，
首先考慮修改，修改分為一下幾個部分： 開頭那段不完整的塊，中間幾段完整的塊，最后那段不完整的塊，
- 對于開頭和后面不完整的塊，我們直接暴力修改 \(a\) 與 \(s\) 陣列，
- 對于中間幾個完整的塊，我們直接給每個塊的 \(b_i\) 加上一個數，
那么，這樣修改，一個數的真實值就是 \(a_i+b_{\text{id}(i)}\) ,其中 \(\text{id}(i)\) ，代表 \(i\) 在哪個塊，
再來考慮詢問操作，詢問也分為三部分：開頭那段不完整的塊，中間幾段完整的塊，最后那段不完整的塊，
- 對于完整的塊，我們直接加上 \(s_i\)，
- 對于不完整的塊中的元素 \(i\)，我們暴力加上 \(a_i+b_{\text{id}(i)}\) ，
查詢和修改可能在同一個塊中，我們特判一下，然后暴力修改/查詢，
于是分塊就完成了！
code
2 分塊進階
還是以一道題引入，
教主的魔法
對于這道題，我們依舊考慮分塊，由于無序的序列再找數的時候很不方便，我們不妨把每個塊都排序，這樣在詢問操作的時候，對于完整的塊，顯然可以二分；對于不完整的塊，我們依舊暴力查找，
現在再來考慮修改操作，由于排完序之后的值的順序是與原陣列不一樣的，但是修改又要是在原來的順序進行修改的，所以，我們還是要保留原陣列，并且還要一個記錄對于單個塊來說，它自己要加上獨立的值，
具體的，如果是對于不完整的塊，我們暴力修改，然后把這個塊重新排序；對于完整的塊，塊內元素的相對大小不變，也就是說，它們的排完序后的順序不變，我們就沒必要再次排序了，在查詢時，再統一加上塊內要統一加的值，這個對于完整的塊的修改操作，類似于線段樹的懶惰標記，
查詢與修改在同一個塊之中的操作，同上，
code
SDOI2008 郁悶的小 J
不知道你們在做這道題的感受如何，反正我是挺郁悶的，當時改了一個下午+一個晚上，倒不是分塊有多難打，而是我錯在輸入問題上！！！在這里，我必須提兩句：以后輸入字符都要用scanf("%s",...) ，而不是 scanf("%c",...) ，我因為這個，RE+TLE，改的真的很久，
好了廢話不多說，讓我們開始分塊（雖然這是個帶修莫隊板子），
顯然對于編號，需要離散化，在這里介紹 gp_hash_table 這個東西，它滿足了我們平常對于 map 的使用，但比 map 更快，然而它是 GNU 的，顯然你要用GNU的編譯器，但 NOI 似乎是開放了帶下劃線的東西，
我們每個塊都來一個標記陣列，那么，對于修改，顯然 \(O(1)\) 暴力；對于查詢，不完整的塊依舊暴力，對于完整的塊，顯然直接 \(O(1)\) 訪問，
code
3 分塊的廣泛運用
LYM之所以說分塊是個好東西，必定有原因，比如像這道題，一個LCT的模板題，分塊也能過！
HNOI2010 彈飛綿羊
你可能會問：怎么能用分塊呢？
顯然也是可以的，只是分塊的思想似乎要改變一下了，我想這道題如果你能獨立思考出來，就說明你對分塊還算熟悉了，你可以把分塊拓展到另外一些題目，所以在看下面的分析之前，希望你先思考5min，
我們不妨令 \(f(i),g(i)\) 分別表示：第 \(i\) 個點需要跳幾次能跳出塊，跳出塊之后的位置在哪里，
那么就非常好做了，筆者覺得要給讀者一些獨立的思考空間，所以在這里，來探討另外一個問題：如何快速求出 \(f(i),g(i)\) ？
顯然你可以用記憶化搜索，但這里有一個 \(O(n)\) 的 dp 的方法，
先來分類討論一下，一個點在跳出塊時有兩種情況：
- 跳一次即可跳出塊，即: \(i+k_i \ge\) 所屬塊的有節點，
- 需要跳幾次，
對于第一種情況，\(f(i)=1,g(i)=i+k_i\) ；對于第二種情況，我們假設 \(j=i+k_i\) ，也就是這個點跳一次后再塊內的位置，假設已經求出 \(f(j),g(j)\)，顯然 \(f(i)=f(j)+1,g(i)=g(j)\) ，
這是不是有點像轉移方程？就是順序有點奇怪，我們只要倒序轉移就好了，
code
4 分塊的時間復雜度
- 對于修改操作，一般對于完整的塊是 \(O(1)\) ，不完整的塊時 \(O(\sqrt{n})\)，至多有2個不完整的塊，所以單次是 \(O(\sqrt{n})\)，
- 對于詢問，和修改類似，一般是 \(O(\sqrt{n})\) ，
所以時間復雜度是 \(O(m\sqrt{n})\) ，還算快，
分塊的時間復雜度取決于你對塊的用法以及一些具體操作，
5 參考文獻
-
分塊思想 - OI Wiki
-
塊狀陣列 - OI Wiki
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501932.html
標籤：其他