MOI 集訓 Week 2——根號分治
DengDuck
·
·
算法·理论
這是澳門信息學代表隊集訓講課的課件，只提供 Sol 而不提供思考過程的解析。
建議先自己思考，再觀看題解，所以所有的 Sol 默認是收起來的。
Part I 數據結構詆毀者
這一部分的內容不需要你掌握一些複雜的數據結構。
P3396 哈希冲突
嘗試思考暴力做法，思考一下，什麼情況下你的做法會比較快？什麼情況下你的做法會比較慢？
::::info[Solution]
$x\leq \sqrt n$ 時我們分出來的不同的類別是很少的，一個位置對應的類別只有 $\sqrt n$ 個，修改時可以暴力改。
所以把查詢分類，不同規模用不同做法。
::::
### 練習題：
- [P9809 [SHOI2006] 作业 Homework。](https://www.luogu.com.cn/problem/P9809)
- [P1483 序列变换。](https://www.luogu.com.cn/problem/P1483)
- [CF1921F Sum of Progression。](https://www.luogu.com.cn/problem/CF1921F)
- [P3591 [POI 2015 R3] 访问 Visits。](https://www.luogu.com.cn/problem/P3591)
## [P2425 小红帽的回文数](https://www.luogu.com.cn/problem/P2425)
我們發現這個問題無法迴避枚舉進制。
意識到自己的無能，往往是通往理性和成功的第一步。
::::info[Solution]
由於求進制是 $\mathcal O(\log n)$ 級別的，我們直覺上可以對於 $2\sim 10^5$ 的進制暴力判定。
否則進制數長度最多為 $2$，存在簡單做法。
::::
## [P8572 [JRKSJ R6] Eltaw](https://www.luogu.com.cn/problem/P8572)
注意到 $n$ 和 $k$ 都可能會很大，但是 $nk\leq 5\times 10^5$。
::::info[Solution]
這啟發我們：$n$ 和 $k$ 不會同時大。
- 當 $k\leq 1000$ 考慮前綴和加暴力。
- 當 $n\leq 1000$ 考慮枚舉所有行中的區間預處理答案。
::::
## [CF1806E Tree Master](https://www.luogu.com.cn/problem/CF1806E)
意識到自己的無能，往往是通往理性和成功的第一步。
::::info[Solution]
直接記憶化搜索即可。
證明是，我們把樹的每一層按照包含的點數分類：
- 對於點數大於 $\sqrt n$ 的層，這樣的層只有最多 $\sqrt n$ 個，而詢問每次只會進過一層一次，所以這一部分時間複雜度為 $\mathcal O(q\sqrt n)$。
- 對於點數小於 $\sqrt n$ 的層，設點數為 $x$，這一層有效的訪問最多只有 $x^2$ 次，用簡單的不等式知識知道把 $n$ 劃分成許多個 $x(x\leq \sqrt n)$，$x^2$ 總和的最大值是 $\mathcal O(n\sqrt n)$ 級別的。
::::
## [P2261 [CQOI2007] 余数求和](https://www.luogu.com.cn/problem/P2261)
模數一直在變化，我們知道這種情況下模是沒有什麼性質的。意識到自己的無能，往往是通往理性和成功的第一步。
因此第一步必然是轉換為整除形式。
$$
\sum_{i=1}^n k\bmod i=\sum_{i=1}^nk-i\lfloor \frac n i \rfloor=nk-\sum_{i=1}^ni\lfloor \frac n i \rfloor
$$
::::info[Solution]
離散函數 $f(x)=\lfloor \frac n x \rfloor$ 的圖像如下：
我們可以證明 $f(x)$ 的取值種類的不嚴格上界為 $2\sqrt n$：
- 對於 $x\leq \sqrt n$，種類上界為 $\sqrt n$ 種。
- 對於 $\sqrt n<x$，$f(x)$ 的取值範圍在 $[1,\sqrt n]$ 範圍內，因此種類上界也是 $\sqrt n$。
顯然每種取值對應的 $x$ 區間是連續的，區間內部我們求解一個等差數列求和即可。
::::
整除分塊往往需要結合一些較難的數論知識，比如莫比烏斯反演，在這裡我們不多贅述，亦不提供練習題。
如果你希望對這個 Trick 有更加深入的理解，可以觀看我的遠古博客：[浅谈整除分块](https://www.cnblogs.com/dengduck/p/17382929.html)。
# Part II 圖論的誘惑
在圖的問題中經常會出現和度數相關的時間複雜度，這類題目很多都可以根號分治。
假如總邊數為 $m$，那麼顯然度數大於 $\sqrt m$ 的點最多只有 $\sqrt m$ 個，我們不妨記這些點為**重點**，其餘點為**輕點**。
以下三道題目我們將可以看到這種思想的運用。
## [ [ABC219G] Propagation](https://www.luogu.com.cn/problem/AT_abc219_g)
我們對於每次操作的流程應該是很明確的：獲得點值——修改其他點。這對做法沒有直接啟發，但你可以想得清晰一些。
::::info[Solution]
輕點有簡單而暴力的做法，那麼我們思考重點怎麼做。
難點大概是我們修改其他點的時候，需要修改的點太多，我們想到可以類似線段樹懶標記的做法——既然我找別人很麻煩，那別人找我不就行了？
我們在點上記錄一下有一個整體操作，然後所有的點在獲得點值的時候要去相鄰的所有重點“領取”這個標記。由於標記可能不唯一，所以我們要記錄標記的產生時間，選擇最新的標記即可。
::::
## [P1989 【模板】无向图三元环计数](https://www.luogu.com.cn/problem/P1989)
我們知道統計無論如何至少要枚舉一條邊。枚舉一個點肯定無法統計。意識到自己的無能，往往是通往理性和成功的第一步。
這裡有一個特別關鍵的轉化，如果你完全沒有頭緒可以點開這條錦囊妙計。
::::info[錦囊妙計]
如果我們把無向圖轉換為有向圖，是否可以使得一些點的出度或者入度控制在某一上界內呢？
::::
::::info[Solution]
如果我們欽定邊為有向邊，方向為度數小的點指向度數大的點：
- 輕點的度數本身就小於 $\sqrt m$。
- 重點只能指向重點，度數無法超過 $\sqrt m$。
我們直接枚舉 $a\to b\to c$ 再判定是否存在邊 $a\to c$，注意到 $a\to b$ 的時間複雜度應該是 $b$ 的度數，所以為 $\mathcal O(\sqrt m)$，而 $a\to b$ 顯然只有 $m$ 條，所以總時間複雜度為 $\mathcal O(m\sqrt m)$。
::::
### 練習題
- [P8250 交友问题。](https://www.luogu.com.cn/problem/P8250)
- [P2500 [SDOI2012] 集合。](https://www.luogu.com.cn/problem/P2500)
- [P6815 [PA 2009] Cakes。](https://www.luogu.com.cn/problem/P6815)
# Part III 數據結構享受者
前置知識：你需要有一定的數據結構基礎（分塊）。
如果你不會分塊，可以嘗試完成前面的練習。因為意識到自己的無能，往往是通往理性和成功的第一步。
## [P5309 [Ynoi2011] 初始化](https://www.luogu.com.cn/problem/P5309)
根號分治似乎都是全局操作，我怎麼才能知道局部得到的貢獻呢？
::::info[Solution]
對於 $x\geq \sqrt n$ 利用分塊維護單點修改區間查詢。
對於 $x\leq \sqrt{n}$ 每一種 $x$ 維護一種分塊，發現只需要維護前 $x$ 項即可，對於整塊貢獻是容易計算的，對於邊界考慮對於修改求前綴和，後綴和，這樣貢獻可以一起求出來。
時間複雜度 $O(n\sqrt n)$。
::::
## [P7710 [Ynoi2077] stdmxeypz](https://www.luogu.com.cn/problem/P7710)
這個問題感覺在樹上完成很沒有前途，怎麼辦呢？
進一步地，根號分治似乎都是全局操作，我怎麼才能只對局部修改呢？
::::info[Solution]
首先樹上查詢一定是不好弄的，考慮求出 $\text{DFS}$ 序，數組每一項記錄其深度。
則問題變成在區間 $[dfn_x,dfn_x+sz_x-1]$ 中 $dep_y\equiv dep_x+a\pmod p$ 的 $y$ 項進行修改（注意這裡的 $a,p$ 是將給出的操作轉換得出的）。
注意到根號分治處理線上問題都是整體操作，這裡卻是區間操作，考慮分塊處理，塊長為 $B$，邊界塊暴力修改。
那我們對於每個區塊操作就相當於整體操作了。
思考 $p\leq k$ 的情況，可以直接打標記，$f_{i,j,k}$ 表示第 $i$ 塊模 $j$ 為 $k$ 的值需要加上的值，一共有 $\dfrac n B$ 塊。
$p\geq k$ 的情況我們發現深度的種類很少,考慮直接維護 $g_{i,j}$ 表示深度為 $i$ 的點在第 $j$ 區塊需要加上的值，
注意到直接做區間加要進行 $\dfrac n k$ 次，直接跑肯定寄，而查詢是單點查詢，所以可以用差分。
時間複雜度為 $\mathcal O\left((B+\dfrac n B+K+\dfrac n K)q\right)$，需要調整區塊長和閾值。
::::