根号算法學習筆記

SDSC Day2，ckw講的根号算法……靜态分塊、動态分塊、莫隊、樹上莫隊、復原莫隊等等。“入墳難度”，ckw如是說。

一、分塊

分塊的本質是分治。與線段樹不同的是，它不是合并兩個兒子，而是合并連續的幾塊。分塊常用于不能“快速合并”的情況。

1. 靜态分塊

内涵就是預處理到塊。

經典的區間衆數（強制線上）思路：

1. 預處理 \(ans[l,r]\) 數組，記錄 \([l,r]\) 塊的資訊（區間衆數）；
2. 對于詢問，如果在一塊内，直接暴力，不超過 \(O(\sqrt n)\) ；
3. 不在一塊内，要麼是 \(ans[bl,br]\) ，要麼在“零散塊”裡出現，是以要統計零散塊裡出現的數字在整個詢問區間 \([l,r]\) 中的出現次數；
4. 枚舉“零散塊”裡的數字已經是 \(O(\sqrt n)\) 級别了——開一個“字首桶”, \(O(1)\) 求出連續塊中的情況，再對“零散塊”開桶跑 \(\sqrt n\) 暴力。

問題是 \(ans\) 數組怎麼求：沒有聽懂 * 1。

2. 動态分塊

有 6 個子問題：

1. 單點修改 \(O(1)\) ，區間查詢 \(O(\sqrt n)\) ;
2. 單點修改 \(O(\sqrt n)\) ，區間查詢 \(O(1)\) ;
3. 區間修改 \(O(1)\) ，單點查詢 \(O(\sqrt n)\) ;
4. 區間修改 \(O(\sqrt n)\) ，單點查詢 \(O(1)\) ;
5. 插入 \(O(1)\) ，求第 \(k\) 小 \(O(\sqrt n)\) ;
6. 插入 \(O(\sqrt n)\) ，求第 \(k\) 小 \(O(1)\) ;

有對應的解決思路：

1. 直接修改；
2. 修改自己塊的和後面塊的，差分；
3. 差分轉化為情況2；
4. 逐塊打标記；
5. 值域分塊；
6. 值域分塊，維護第 \(k\) 小在第幾塊和每一塊内的數。

二、莫隊

1. 莫隊

P1972 HH 的項鍊（72分）。離線下，從一個詢問區間轉移到下一個——排序詢問，存在一種詢問序列，使得這個暴力達到 \(O(n \sqrt n)\) 級别。

排序方式：分塊，以左端點所在塊為第一關鍵字，右端點為第二關鍵字。

為什麼是對的？分類讨論。

1. \(l_i\) 和 \(l_{i+1}\) 在同一塊内：時間複雜度為 \(O(|l_i-l_{i+1}|+|r_i|)\) ,前者 \(O(\sqrt n)\) 級别，後者加起來 \(O(n)\) 。
2. \(l_i\) 和 \(l_{i+1}\) 不在同一塊内：加起來 \(O(n)\) 。

1/2 常數優化：奇偶性分，右端點從小到大還是從大到小。

用值域分塊平衡複雜度：沒有聽懂 * 2 。

2. 樹上莫隊

将樹化為鍊，轉為普通莫隊。

寫出“入棧出棧序”，如果 \(x\) 是 \(y\) 的 LCA ，則取出 \(fir_x\) 到 \(fir_y\) ，否則取出 \(fir_x\) 到 \(sec_y\) 。取出的序列中出現奇數次的點在 \(x\) 到 \(y\) 的路徑上，否則不在。注意，會漏掉 LCA ，要補上。

3. 復原莫隊