or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
SQRT-Decomposition
Introduction to Competitive Programming
2022/03/30
分塊(SQRT-Decomposition)
如其英文名,根號分解
一種資料結構
用於區間操作,區間詢問之類的問題
將序列分成每塊大小為\(\lfloor \sqrt{n} \rfloor\),而總共\(\lceil \frac{n}{ \lfloor \sqrt{n} \rfloor } \rceil\)塊
以 \(n=10\) 為例
每塊大小為\(\lfloor \sqrt{n} \rfloor = 3\),總共 \(\lceil \frac{n}{ \lfloor \sqrt{n} \rfloor } \rceil = 4\)塊
預處理
(假設要求區間總和)
區間加值
假設區間 1~9 加值 5
最左塊
最左邊那塊每格暴力跑過去加值
中間每塊
在中間每格的 TAG 加值
最右塊
最右邊那塊每格暴力跑過去加值
區間加值
假設區間 1~9 加值 5
會發現最右邊那塊裡面每格都有選到
但是為了方便實作,因此最右邊那格會直接暴力加
區間加值
(假設要求區間總和)
詢問
(假設要求區間總和)
做法與區間加值相同,分最左、中間每塊、最右
以詢問區間 2-8 為例
詢問
(假設要求區間總和)
複雜度分析
建表
\(O(n)\), 一個一個跑過去就好
更新
最左的那塊裡面最多跑過 \(\sqrt{n}\) 格
中間跑過最多 \(\sqrt{n}\) 大塊
最右的那塊裡面最多跑過 \(\sqrt{n}\) 格
複雜度 \(O(\sqrt{n})\)
詢問
同上
複雜度 \(O(\sqrt{n})\)
結論
分塊看起來複雜度比線段樹差
但分塊用迴圈實作常數比較小(線段樹遞迴常數較大)
實際上大部分題目都還是可以過的
\(n = 2 \cdot 10^5 , n \sqrt{n} = 89,442,719\)
熟悉之後,實作複雜度不比線段樹高
而且能解出更多線段樹解不出來的題目
莫隊算法(mo's algorithm)
是2009年中國國家代表隊「莫濤」所提出來的
一種運用到分塊概念的離線演算法
使用條件
用於序列的區間詢問
對於詢問的 \([l,r]\) 區間,如果已經計算好區間內的答案
並且能在 \(O(1)\) 或者 \(O(lgN)\) 的複雜度內,計算轉移到區間的答案
\([l,r+1], [l,r-1], [l+1,r], [l-1,r]\) (即 \([l,r]\) 左界或右界移動一格)
則可以在\(O(N\sqrt{N})\)的複雜度內求出所有詢問的答案
引入問題
SPOJ-DQUERY
給你一個大小為 \(n(n\le3 \cdot 10^4)\) 的序列 \(a (1\le a_i\le10^6)\)
\(q(q\le200000)\) 筆詢問,每次問你區間 \([l,r]\) 內,有幾個不同的數字
如果每次都直接暴力找,最差複雜度 \(O(NQ) \rightarrow\) TLE
作法
將所有詢問分塊之後各自排序,依序暴力從前一個詢問區間計算完答案轉移到下一個詢問區間求出答案
將所有詢問依照先依照左界 \(l\) 去分塊,
\(\frac{l}{\lfloor\sqrt{n}\rfloor}\) 一樣的在同一塊,而同一塊的分別再各自用右界 \(r\) 去排序
排序詢問
假設序列長度為 \(10 (i \in 0 \sim 9)\) , 每格大小為 \(\lfloor\sqrt{10}\rfloor = 3\)
詢問有 [4, 8], [2, 3], [9, 9], [0, 7], [1, 2], [6, 9], [7, 8]
將詢問排序 (先比較塊的順序,再比較右界大小)
[1, 2], [2, 3], [0, 7], [4, 8], [7, 8], [6, 9], [9, 9]
暴力轉移
從前一個區間轉移到下一個區間,每次移動一格
以 區間 [0, 7] 轉移到區間 [4, 8]
[0, 7] \(\to\) [0, 8] \(\to\) [1, 8] \(\to\) [2, 8] \(\to\) [3, 8] \(\to\) [4, 8]
一次 新增/刪除 一個元素
暴力轉移
計算新增/刪除元素
不同題目新增/移除元素做法不同,以例題來說
給你一個大小為 \(n(n\le3 \cdot 10^4)\) 的序列 \(a (1\le a_i\le10^6)\)
每次問你區間 \([l,r]\) 內,有幾個不同的數字 ?
直接開一個值域大小的陣列 cnt[1000005],計算每個數字出現的次數
新增元素 add(x) 直接 cnt[x]+=1,並且判斷是不是原本為 0 ,若為 0 則個數 +1
移除元素 sub(x) 則為 cnt[x]-=1,移除後判斷是否變為 0 ,若為 0 則個數 -1
每次更新複雜度 \(O(1)\)
計算新增/刪除元素
複雜度分析
\(n\) 為序列總長度,
\(q\) 為詢問比數,
\(p\) 為移動一格的複雜度
移動加起來為 \(q\sqrt{n} + n\sqrt{n} + n\)
複雜度為 \(O(p(q+n)\sqrt{n})\)
其他優化
排序的時候,在同一塊的詢問區間會用右界排序
在同一塊的最後面右界會最大,而到了下一塊的右界
當換到下一塊的時候右界又回到最小開始,增加移動次數
而如果換不同塊的時候,右界大小關係交替(小於\(\to\)大於\(\to\)小於\(\to\)大於)
就能省去一些常數的時間
Question Time and Practice
Homework Link
提交期限到下星期三 4/6 23:59 截止