<style>
.reveal .slides {
font: 0.65em "Fira Mono", monospace;
}
.yellow {
color: yellow;
}
</style>
# 根號算法 I
#### **Gino**
---
## 內容大綱
- ★☆☆☆☆ 序列分塊 — 暖身
- ★★★☆☆ 序列分塊 — 實戰
- ★★☆☆☆ 值域分塊
- ★★★★★ 根號分 case
---
# [完整題單在此](https://hackmd.io/@penguin71630/r1Q1Ite_c)
---
<!-- #################################################### -->
## 序列分塊 — 暖身
----
### 例題們
- [單點修改區間和](https://cses.fi/problemset/task/1648)
- [區間修改區間和](https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/D)
----
我不打算直接先介紹分塊的原理
我覺得透過問題來講解會更好懂
所以先來點大家都會的 RMQ 當暖身 OwO<!-- .element: class="fragment" data-fragment-index="1" -->
----
### [單點修改區間和](https://cses.fi/problemset/task/1648)
給一個長度為 $N$ 的陣列，你需要處理 $Q$ 筆詢問。詢問有兩種：
1. **修改**：把第 $k$ 個位置的值改成 $u$。
2. **詢問**：詢問區間 $[a, b]$ 的和。
$N, Q \leq 2 \times 10^5$
----
先假設你今天完全不會 BIT／線段樹
看到這個問題，你會怎麼做來加速 $O(NQ)$ 的作法？<!-- .element: class="fragment" data-fragment-index="1" -->
----
$O(NQ)$ 慢的地方在於，每次詢問都要一格一格慢慢掃過整個區間。
那要不要試試看把數字「分組」？<!-- .element: class="fragment" data-fragment-index="1" -->
維護好每一個組的總和，這樣詢問的時候就不用一格一格掃，而是一組一組掃。<!-- .element: class="fragment" data-fragment-index="2" -->
P.S. 分組 = 分塊<!-- .element: class="fragment" data-fragment-index="3" -->
----
- 將序列每 $B$ 個數字分成一組（$B$ 是自己決定的數字）
- 每組額外維護整組內所有數字的和<!-- .element: class="fragment" data-fragment-index="1" -->
<!-- .element: class="fragment" data-fragment-index="2" -->
###### 上圖以 $B = 3$ 為例<!-- .element: class="fragment" data-fragment-index="2" -->
----
- 對於第二種操作（詢問 $[l, r]$ 的區間和）
- 我們可以將 $[l, r]$ 拆成開頭一些零碎的數字 + 中間一些塊 + 結尾一些零碎的數字
----
- 以詢問 [2, 11] 為例
- 我們可以把它拆成 5 + 1 + **[3 2 4]** + **[8 7 6]** + 3 + 1<!-- .element: class="fragment" data-fragment-index="1" -->
- 於是算答案的時候，我們直接掃過<!-- .element: class="fragment" data-fragment-index="2" -->
- 開頭一些零碎的數字 (5 1)<!-- .element: class="fragment" data-fragment-index="3" -->
- 中間的塊 (**[3 2 4]** **[8 7 6]**)<!-- .element: class="fragment" data-fragment-index="4" -->
- 結尾一些零碎的數字 (3 1)<!-- .element: class="fragment" data-fragment-index="5" -->
###### $5 + 1 + 9 + 21 + 3 + 1 = 40$<!-- .element: class="fragment" data-fragment-index="6" -->
----
- 修改的話，直接 $O(1)$ 更新原本的陣列還有其所在的塊的答案。
----
- 假設把第 5 個數字修改成 10，見下圖：
----
### 時間複雜度
- 預先處理每塊的資訊：$O(N)$。<!-- .element: class="fragment" data-fragment-index="1" -->
- 一次修改：$O(O(1))$。<!-- .element: class="fragment" data-fragment-index="2" -->
- 一次詢問：掃過開頭跟結尾不完整的塊 $O(B)$ + 中間的塊 $O(\frac{N}{B})$。<!-- .element: class="fragment" data-fragment-index="3" -->
總時間複雜度：$O(N + Q (B + \frac{N}{B}))$。<!-- .element: class="fragment" data-fragment-index="4" -->
----
### $B$ 怎麼決定
$B$ 如果取太小的話（例如 2 之類的）會發現效率上還是很差
因為你還是要掃過很多東西才能算答案
----
### $B$ 怎麼決定
可是 $B$ 如果取太大的話（例如 $N$ 的一半之類的）會發現幾乎用不到塊的答案
有維護跟沒有一樣
----
感覺上好像有個中間點...？
----
「總時間複雜度：$O(N + Q (B + \frac{N}{B}))$」
中間這條 $B + \frac{N}{B}$ 是一個 U 型函數（有最小值）
----
而算幾不等式告訴我們
$B + \frac{N}{B}$ 的最小值發生在 $B = \sqrt{N}$ 的時候<!-- .element: class="fragment" data-fragment-index="1" -->
故令 $B = \sqrt{N}$ 可得最佳複雜度 $O(N + Q \sqrt{N})$。<!-- .element: class="fragment" data-fragment-index="2" -->
----
$N, Q \leq 2 \times 10^5$
$Q \sqrt{N}$ 大概是<!-- .element: class="fragment" data-fragment-index="1" --> $9 \times 10^7$<!-- .element: class="fragment" data-fragment-index="1" -->
但分塊常數很小，因此這樣還是可以過的<!-- .element: class="fragment" data-fragment-index="2" -->
<!-- .element: class="fragment" data-fragment-index="2" -->
###### Code：<!-- .element: class="fragment" data-fragment-index="2" -->https://cses.fi/paste/d6e8d376cbc86fca3c5719/<!-- .element: class="fragment" data-fragment-index="2" -->
----
### 實作
- 陣列還有塊都從 0 開始編號<!-- .element: class="fragment" data-fragment-index="1" -->
- 第 i 個數字所屬的塊編號是 i/B<!-- .element: class="fragment" data-fragment-index="2" -->
- 第 k 個塊的開頭是 k × B<!-- .element: class="fragment" data-fragment-index="3" -->
----
### 實作
- 詢問區間 [l, r] 的時候要分兩種情況
- l 跟 r 在同一塊 (l/B == r/B)：暴力從 l 掃到 r<!-- .element: class="fragment" data-fragment-index="1" -->
<!-- .element: class="fragment" data-fragment-index="1" -->
- l 跟 r 不在同一塊：開頭 + 中間 + 結尾<!-- .element: class="fragment" data-fragment-index="2" -->
<!-- .element: class="fragment" data-fragment-index="2" -->
----
### 實作
```cpp=
int N, Q;
vector<long long> v;
int B; // B 是一個塊的大小
vector<ll> blks; // 維護每一塊的答案
void init() {
cin >> N >> Q;
B = sqrt(N);
v.clear(); v.resize(N);
for (auto& i : v) cin >> i;
blks.clear(); blks.resize(N/B+1, 0);
for (int i = 0; i < N; i++) {
// 塊從 0 開始編號
// 第 i 個位置屬於第 i/B 個塊
blks[i/B] += v[i];
}
}
void solve() {
while (Q--) {
int op; cin >> op;
if (op == 1) {
/* 修改 */
int k; long long u;
cin >> k >> u; k--;
blks[k/B] += (u - v[k]); // 更新塊的答案
v[k] = u; // 更新原本陣列的答案
} else {
/* 詢問 */
int l, r; cin >> l >> r; l--, r--;
long long ans = 0;
if (l/B == r/B) {
// 特判：如果詢問左界跟右界在同一塊，那就直接暴力做
for (int i = l; i <= r; i++) ans += v[i];
} else {
// 先掃過開頭零碎的一些數字
for (int i = l; i < B*(l/B+1); i++) ans += v[i];
// 再掃過中間的塊
for (int bi = l/B+1; bi < r/B; bi++) ans += blks[bi];
// 最後掃過結尾零碎的一些數字
for (int i = B*(r/B); i <= r; i++) ans += v[i];
}
cout << ans << endl;
}
}
}
```
----
### [區間修改區間和](https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/D)
給一個長度為 $N$ 的陣列，一開始全部為 0，你需要處理 $M$ 筆詢問。詢問有兩種：
1. **修改**：把區間 $[l, r)$ 的所有值加上 $v$。
2. **詢問**：詢問區間 $[l, r)$ 的和。
$N, Q \leq 10^5$
----
一樣把序列每 $O(\sqrt{N})$ 個切成一塊
----
跟上一題類似，只不過單點修改變成區間修改。
還記得懶標線段樹怎麼寫嗎？<!-- .element: class="fragment" data-fragment-index="1" -->
----
- 我們一樣用懶標的想法
- 當修改的區間包含某個完整的塊時<!-- .element: class="fragment" data-fragment-index="1" -->
- 就在那個塊打上懶標<!-- .element: class="fragment" data-fragment-index="1" -->
- 懶標的意義是「那一塊裡面的所有數字都要更新」<!-- .element: class="fragment" data-fragment-index="2" -->
----
- 修改某個區間 $[l, r]$ 時
- 一樣可以把 $[l, r]$ 拆成一些零碎的數字 + 中間一些完整的塊 + 結尾一些零碎的數字
- **零碎的數字** $\Rightarrow$ 暴力修改<!-- .element: class="fragment" data-fragment-index="1" -->
- **完整的塊**<!-- .element: class="fragment" data-fragment-index="2" --> $\Rightarrow$<!-- .element: class="fragment" data-fragment-index="2" --> <span class="yellow">修改塊的答案，並打上懶標</span><!-- .element: class="fragment" data-fragment-index="2" -->
----
- 詢問某個區間 $[l, r]$ 時
- 一樣可以把 $[l, r]$ 拆成一些零碎的數字 + 中間一些完整的塊 + 結尾一些零碎的數字
- **零碎的數字** $\Rightarrow$ $O(\sqrt{N})$ 暴力下推該塊的懶標、暴力詢問<!-- .element: class="fragment" data-fragment-index="1" -->
- **完整的塊**<!-- .element: class="fragment" data-fragment-index="2" --> $\Rightarrow$<!-- .element: class="fragment" data-fragment-index="2" --> <span class="yellow">不用推懶標</span>，直接拿塊的答案<!-- .element: class="fragment" data-fragment-index="2" -->
----
### 時間複雜度
- <span class="yellow">**預先處理每塊的資訊**：$O(N)$</span><!-- .element: class="fragment" data-fragment-index="1" -->
- <span class="yellow">**一次修改**：$O(\sqrt{N})$</span><!-- .element: class="fragment" data-fragment-index="2" -->
- 暴力更新開頭跟結尾不完整的塊：$O(\sqrt{N})$。<!-- .element: class="fragment" data-fragment-index="3" -->
- 掃過中間 $O(\sqrt{N})$ 個塊，$O(1)$ 打上懶標：$O(\sqrt{N})$。<!-- .element: class="fragment" data-fragment-index="4" -->
- <span class="yellow">**一次詢問**：$O(\sqrt{N})$</span><!-- .element: class="fragment" data-fragment-index="5" -->
- 掃過開頭跟結尾不完整的塊 + 下推懶標：$O(\sqrt{N})$。<!-- .element: class="fragment" data-fragment-index="6" -->
- 掃過中間的塊：$O(\sqrt{N})$。<!-- .element: class="fragment" data-fragment-index="7" -->
<span class="yellow">總時間複雜度：$O(N + Q \sqrt{N})$</span><!-- .element: class="fragment" data-fragment-index="8" -->
----
搞不太懂？舉個栗子
- $N = 11, \langle a_N \rangle = [2, 5, 1, 3, 2, 4, 8, 7, 6, 3, 1, 9]$
----
- 將區間 $[2, 11]$ 加上 $5$
----
- 將區間 $[2, 11]$ 加上 $5$
###### 不完整的塊：暴力更新／完整的塊：打懶標
----
- 將區間 $[2, 11]$ 加上 $5$
----
- 將區間 $[1, 10]$ 加上 $3$
----
- 將區間 $[1, 10]$ 加上 $3$
###### 不完整的塊：暴力更新／完整的塊：打懶標
----
- 將區間 $[1, 10]$ 加上 $3$
----
- 詢問區間 $[2, 11]$ 的和
----
- 詢問區間 $[2, 11]$ 的和
###### 對於不完整的塊，先暴力下推那些塊的懶標
----
- 詢問區間 $[2, 11]$ 的和
----
- 詢問區間 $[2, 11]$ 的和
###### 接下來處理詢問，對於不完整的塊暴力算，完整的直接拿該塊的答案，不用理會懶標
----
- 詢問區間 $[2, 8]$ 的和
----
- 詢問區間 $[2, 8]$ 的和
###### 對於不完整的塊，先暴力下推那些塊的懶標
----
- 詢問區間 $[2, 8]$ 的和
----
- 詢問區間 $[2, 8]$ 的和
###### 接下來處理詢問，對於不完整的塊暴力算，完整的直接拿該塊的答案，不用理會懶標
----
```cpp=
int n, q, B;
vector<ll> v;
vector<ll> blks, tag;
void init() {
cin >> n >> q;
B = (int)sqrt(n);
v.clear(); v.resize(n, 0);
blks.clear(); blks.resize(n/B + (n%B != 0), 0);
tag.clear(); tag.resize(n/B + (n%B != 0), 0);
}
inline int len(int l, int r) {
return r-l+1;
}
inline void push(int id) {
for (int i = B*id; i < min(B*(id+1), n); i++) v[i] += tag[id];
tag[id] = 0;
}
void solve() {
while (q--) {
int op; cin >> op;
if (op == 1) {
int l, r; ll x;
cin >> l >> r >> x; r--;
if (l/B == r/B) {
for (int i = l; i <= r; i++) {
v[i] += x;
blks[l/B] += x;
}
} else {
for (int i = l; i < B*(l/B+1); i++) {
v[i] += x;
blks[l/B] += x;
}
for (int bi = l/B+1; bi < r/B; bi++) {
tag[bi] += x;
blks[bi] += x * len(B*bi, min(n-1, B*(bi+1)-1));
}
for (int i = B*(r/B); i <= r; i++) {
v[i] += x;
blks[i/B] += x;
}
}
} else {
int l, r; cin >> l >> r; r--;
ll ans = 0;
if (l/B == r/B) {
if (tag[l/B]) push(l/B);
for (int i = l; i <= r; i++) ans += v[i];
} else {
if (tag[l/B]) push(l/B);
for (int i = l; i < B*(l/B+1); i++) {
ans += v[i];
}
for (int bi = l/B+1; bi < r/B; bi++) {
ans += blks[bi];
}
if (tag[r/B]) push(r/B);
for (int i = B*(r/B); i <= r; i++) {
ans += v[i];
}
}
cout << ans << endl;
}
}
}
```
---
## 重點思路整理
----
跟分治型資料結構（BIT／線段樹）不同
分塊算是暴力的改進<!-- .element: class="fragment" data-fragment-index="1" -->
透過把序列分組的方法巧妙地讓複雜度降到可以在時限內 AC<!-- .element: class="fragment" data-fragment-index="2" -->
這也是今天的主題「根號算法」的由來<!-- .element: class="fragment" data-fragment-index="2" -->
而且分塊的實作比較容易，常數也小<!-- .element: class="fragment" data-fragment-index="3" -->
在 $N$ 不算太大的時候（$10^5$ 以下）<!-- .element: class="fragment" data-fragment-index="4" -->
執行時間往往能和線段樹並駕齊驅甚至更少<!-- .element: class="fragment" data-fragment-index="5" -->
所以不失為一個平常解題可以考慮的方法 OwO<!-- .element: class="fragment" data-fragment-index="6" -->
---
## 休息 10 分鐘／提問
---
## 序列分塊 — 實戰
----
### 例題們
- [Holes](https://codeforces.com/problemset/problem/13/E)
- [中國人插隊問題](https://neoj.sprout.tw/problem/213/)
- [Anton and Permutation](https://codeforces.com/problemset/problem/785/E)
----
### [Holes](https://codeforces.com/problemset/problem/13/E)
地面上有 $N$ 個彈簧床排成一列，由左到右編號 $1 \sim N$。
每個彈簧床的彈力為 $a_i$，能讓球從第 $i$ 個位置彈到第 $i + a_i$ 個位置。
接下來有 $M$ 個事件發生。
- 0 a b：第 a 個彈簧床的彈力改為 b。
- 1 a：在第 a 個彈簧床丟一顆球，輸出它最後碰到的彈簧床編號 + 它彈了幾次。
$N, M \leq 10^5$
----
### [中國人插隊問題](https://neoj.sprout.tw/problem/213/)
一開始有 $N$ 個人排成一個隊伍，接下來有 $M$ 個事件發生。
- ADD i x：編號為 x 的人插隊到第 i 個位置
- LEAVE i：第 i 個位置的人離開隊伍
- QUERY i：輸出第 i 個位置的人的編號
$N, M \leq 10^5$
----
### [Anton and Permutation](https://codeforces.com/problemset/problem/785/E)
給你一個長度為 $N$ 的序列 $\langle a_N \rangle$，一開始 $\langle a_N \rangle = [1, 2, ..., N]$。
接下來會有 $Q$ 個操作。
每個操作會給兩個數字 $l, r \ (l < r)$，代表要交換 $a_l$ 和 $a_r$。
請在每次操作完後輸出整個序列有多少個逆敘數對。
$N \leq 2 \times 10^5, \ Q \leq 5 \times 10^4$
---
## 值域分塊
----
### 例題們
- [第 Z 小](https://neoj.sprout.tw/problem/742/)
- (No Judge) 數列第 $k$ 小
----
### [第 Z 小](https://neoj.sprout.tw/problem/742/)
你有一個容器，一開始沒有任何東西，接下來會有 $Q$ 次操作。
- 1 x y：**[加值]** 把 y 個 x 加入容器
- 2 x y：**[刪除]** 把 y 個 x 從容器刪除
- 3 z：查詢第 z 小的數字
$Q, x \leq 10^5$
$y \leq 10^9$
----
這題數字個數可能很大，但值域很小
直接用陣列紀錄每個數字出現幾次！<!-- .element: class="fragment" data-fragment-index="1" -->
----
- 開一個陣列 cnt[x] 紀錄目前有多少個數字 x
- 加值跟刪除直接 $O(1)$ 改 cnt[x]<!-- .element: class="fragment" data-fragment-index="1" -->
- 查詢？<!-- .element: class="fragment" data-fragment-index="2" -->
----
- 把值域每 $O(\sqrt{N})$ 個切成一塊（切 cnt 陣列）。
- 查詢的時候先查大塊，看第 z 個數字落在哪一塊，接著暴力查詢那一塊，找到第 z 個的具體位置。<!-- .element: class="fragment" data-fragment-index="1" -->
- 大塊最多 $O(\sqrt{N})$ 個，小塊也只有 $O(\sqrt{N})$ 個數字。<!-- .element: class="fragment" data-fragment-index="2" -->
- 因此單次查詢複雜度 $O(\sqrt{N})$。<!-- .element: class="fragment" data-fragment-index="3" -->
- 總時間複雜度 $O(N + M\sqrt{N})$。<!-- .element: class="fragment" data-fragment-index="4" -->
----
```cpp=
int q, k;
ll arr[maxn], b[maxn];
inline void modify(int x, ll val) {
arr[x] += val;
b[x/k] += val;
}
inline int query(ll z) {
int bi, i;
ll cnt = 0;
for (bi = 0; cnt + b[bi] < z; bi++) cnt += b[bi];
for (i = bi*k; cnt + arr[i] < z; i++) cnt += arr[i];
return i;
}
int main() {
fastio
cin >> q;
k = (int)sqrt(100000) + 1;
while (q--) {
int md; cin >> md;
if (md == 1) {
int x; ll val;
cin >> x >> val;
modify(x, val);
} else if (md == 2) {
int x; ll val;
cin >> x >> val;
modify(x, -val);
} else {
ll z; cin >> z;
cout << query(z) << endl;
}
}
return 0;
}
```
----
### (NoJudge) 數列第 $k$ 小
給你 $N, x, a, b$，現有一個長度為 $N$ 的數列由以下方式生成：
- $s_1 = x$
- $s_{i+1} = (a \cdot s_{i} + b) \ \mathrm{mod} \ (10^9+7)$
有 $Q$ 筆詢問，每筆詢問給一個 $k \ (1 \leq k \leq N)$，請輸出此數列第 $k$ 小的數字。
- $1 \leq N \leq 2 \times 10^7, 1 \leq Q \leq 20$
- 時間限制：10 秒，**記憶體限制：1MB**
---
## 休息 10 分鐘／提問
---
## 根號分 case
----
有些問題可能存在兩種或以上的作法
而每種作法各有優缺點<!-- .element: class="fragment" data-fragment-index="1" -->
缺點是指在某些情況下該作法會 TLE 或 MLE<!-- .element: class="fragment" data-fragment-index="2" -->
----
接下來要教大家的解題技巧
概括來說是當這樣的問題（存在兩解或多解）出現時<!-- .element: class="fragment" data-fragment-index="1" -->
我們可以取彼所長，合併兩種解<!-- .element: class="fragment" data-fragment-index="2" -->
最終會很神奇地得到通往複雜度夠好的解法<!-- .element: class="fragment" data-fragment-index="3" -->
----
我這樣講你們聽得懂才怪
直接看例題就知道我在說什麼了
OwO
---
## 根號分 case — 例題
----
### 例題們
- [Array Queries](https://codeforces.com/contest/797/problem/E)
- [背包問題](https://neoj.sprout.tw/problem/743/)
- [Counting Triangles](https://neoj.sprout.tw/problem/252/)
----
### [Array Queries](https://codeforces.com/contest/797/problem/E)
給長度為 $N$ 的正整數序列 $a$，接下來你要回答 $Q$ 筆詢問。
每筆詢問給 $p, k$。
有個變數 $x$ 一開始設為 $p$，每隔一秒 $x$ 就會變成 $x + a_x + k$。
輸出經過幾秒後 $x$ 會大於 $N$？
$1 \leq N, Q \leq 10^5$
- 子題一：所有詢問的<!-- .element: class="fragment" data-fragment-index="1" --> $k = 0$ <!-- .element: class="fragment" data-fragment-index="1" -->
- 子題二：所有詢問的<!-- .element: class="fragment" data-fragment-index="1" --> $k \leq 400$ <!-- .element: class="fragment" data-fragment-index="1" -->
- 子題三：無其他限制 <!-- .element: class="fragment" data-fragment-index="1" -->
----
### 子題一：所有詢問的 $k = 0$
- 「$x$ 一開始設為 $p$，每隔一秒 $x$ 就會變成 $x + a_x$」<!-- .element: class="fragment" data-fragment-index="1" -->
- dp[i] 代表 $x$ 等於 i 的時候再過幾秒就會大於 <!-- .element: class="fragment" data-fragment-index="2" --> $N$ <!-- .element: class="fragment" data-fragment-index="2" -->
- 倒著做 dp（從 dp[N] 做到 dp[1]）<!-- .element: class="fragment" data-fragment-index="3" -->
- if (i + a[i] > N) dp[i] = 1;<!-- .element: class="fragment" data-fragment-index="3" -->
- else dp[i] = dp[i + a[i]] + 1;<!-- .element: class="fragment" data-fragment-index="3" -->
- $O(N + Q)$<!-- .element: class="fragment" data-fragment-index="4" -->
----
### 子題二：所有詢問的 $k \leq 400$
- 注意到 $400 \times 10^5 = 4 \times 10^7$，在時間和空間限制內。<!-- .element: class="fragment" data-fragment-index="1" -->
- 對每個可能的 $k$（1 到 400）預先蓋好 dp 陣列。<!-- .element: class="fragment" data-fragment-index="2" -->
- 詢問的時候就可以 $O(1)$ 輸出答案。<!-- .element: class="fragment" data-fragment-index="3" -->
- $O(Nk + Q)$<!-- .element: class="fragment" data-fragment-index="4" -->
----
### 子題三：$k$ 有可能很大
- 沒辦法對每個可能的 $k$ 預處理 dp 陣列，會噴到 $O(N^2)$。<!-- .element: class="fragment" data-fragment-index="1" -->
- 但我們可以延續上個子題的想法。<!-- .element: class="fragment" data-fragment-index="2" -->
- 對於夠小的 $k$ 我們一樣預處理 dp。<!-- .element: class="fragment" data-fragment-index="3" -->
- 大的 $k$ 呢？<!-- .element: class="fragment" data-fragment-index="4" -->
----
### 子題三：$k$ 有可能很大
- 大的 $k$ 呢？
- 有發現嗎，$k$ 越來越大代表 $x$ 很快就會大於 $N$。
### 暴力算答案！<!-- .element: class="fragment" data-fragment-index="1" -->
----
- 我們以 $\sqrt{N}$ 為分界。
- <span class="yellow">對於 $\leq \sqrt{N}$ 的 $k$ 預處理 dp 陣列。</span><!-- .element: class="fragment" data-fragment-index="1" -->
- 複雜度 $O(N \sqrt{N})$。<!-- .element: class="fragment" data-fragment-index="2" -->
- <span class="yellow">對於 $> \sqrt{N}$ 的 $k$ 暴力算答案。</span><!-- .element: class="fragment" data-fragment-index="3" -->
- 答案不會超過 $\sqrt{N}$，因此暴力複雜度是 $O(Q \sqrt{N})$。<!-- .element: class="fragment" data-fragment-index="4" -->
- $O((N + Q) \sqrt{N})$<!-- .element: class="fragment" data-fragment-index="5" -->
###### Code：<!-- .element: class="fragment" data-fragment-index="6" -->https://codeforces.com/contest/797/submission/157664240<!-- .element: class="fragment" data-fragment-index="6" -->
----
### [背包問題](https://neoj.sprout.tw/problem/743/)
給你 $N$ 個正整數 $a_1, a_2, ..., a_N$，這 $N$ 個正整數總和為 $K$。
請分別判斷對於 $1 \sim K$ 的每個正整數，是否可以從這 $N$ 個數選一些數湊出來。
$N, K \leq 2 \times 10^5$
----
直接做 0/1 背包？
$O(NK) \Longrightarrow$ TLE<!-- .element: class="fragment" data-fragment-index="1" -->
----
### 奇怪的條件
$a_1 + a_2 + ... + a_N = K$ 而且 $K \leq 2 \times 10^5$
----
### 重要性質
如果我們以 $\sqrt{K}$ 為分界點，把 $a_i$ 分成 $\leq \sqrt{K}$ 和 $> \sqrt{K}$
那麼會得到一個重要的性質：<span class="yellow">$> \sqrt{K}$ 的數字最多只會有 $\sqrt{K}$ 個！</span><!-- .element: class="fragment" data-fragment-index="1" -->
----
- 小數字 ($\leq \sqrt{K}$) 種類不多，最多只會有 $\sqrt{K}$ 種數字
- <span class="yellow">對小數字做有限背包</span><!-- .element: class="fragment" data-fragment-index="2" --><span class="yellow">，複雜度 $O(K \sqrt{K})$</span><!-- .element: class="fragment" data-fragment-index="3" -->
- 大數字 ($> \sqrt{K}$) 個數不多，最多只會有 $\sqrt{K}$ 個數字<!-- .element: class="fragment" data-fragment-index="1" -->
- <span class="yellow">對大數字做 0/1 背包</span><!-- .element: class="fragment" data-fragment-index="2" --><span class="yellow">，複雜度 $O(K \sqrt{K})$</span><!-- .element: class="fragment" data-fragment-index="3" -->
----
總時間複雜度 $O(K \sqrt{K})$
----
根據 $a_1 + a_2 + ... + a_N = K$ 還可以得到一個重要性質：
### $a_i$ 的種類少於 $\sqrt{K}$ 種<!-- .element: class="fragment" data-fragment-index="1" -->
如果種類超過 $\sqrt{K}$ 種，那 $a_1 + ... + a_N$ 無論如何都會 $> K$，和題目矛盾<!-- .element: class="fragment" data-fragment-index="2" -->
----
### 另解
因此原本的題目我們可以直接用有限背包做，不用對數字分大小<!-- .element: class="fragment" data-fragment-index="1" -->
複雜度依然是 $O(K \sqrt{K})$。<!-- .element: class="fragment" data-fragment-index="2" -->
----
### [Counting Triangles](https://neoj.sprout.tw/problem/252/)
給一張 $N$ 點 $M$ 邊的簡單無向圖，請算出這張圖有幾個「三角形」？
三角形是指一組數對 $(x, y, z)$ 滿足 $(x, y)$、$(y, z)$、$(z, x)$ 都有邊連接。
$N, M \leq 10^5$
----
### 核心想法
- 枚舉其中一個點，固定這個點之後枚舉剩下兩個點<!-- .element: class="fragment" data-fragment-index="1" -->
- 同個三角形會被重複算三次（因為三角形有三個頂點）<!-- .element: class="fragment" data-fragment-index="2" -->
- 枚舉完所有點以後答案除以 3 才是正確答案<!-- .element: class="fragment" data-fragment-index="3" -->
----
### 重要假設
- 方便講解，假設我們能快速回答兩個點 $(u, v)$ 是否有邊連接（$O(1)$ 或 $O(\log N)$ 之類的）
- 具體怎麼做等等會說明<!-- .element: class="fragment" data-fragment-index="1" -->
----
### 作法一
- 枚舉每一個點 $u$ 當頂點<!-- .element: class="fragment" data-fragment-index="1" -->
- 然後枚舉其中兩個 $u$ 的鄰居，檢查他們有沒有邊連接<!-- .element: class="fragment" data-fragment-index="2" -->
- 有的話就是一個三角形<!-- .element: class="fragment" data-fragment-index="2" -->
- $O(d_u^2)$，其中 $d_u$ 是 $u$ 的點度<!-- .element: class="fragment" data-fragment-index="4" -->
<!-- .element: class="fragment" data-fragment-index="3" -->
----
### 作法二
- 一樣枚舉每一個點 $u$ 當頂點<!-- .element: class="fragment" data-fragment-index="1" -->
- 然後枚舉圖上的每條邊，檢查它的兩個端點有沒有都跟 $u$ 連接<!-- .element: class="fragment" data-fragment-index="2" -->
- 有的話就是一個三角形<!-- .element: class="fragment" data-fragment-index="2" -->
- $O(M)$，$M$ 是整張圖的邊數<!-- .element: class="fragment" data-fragment-index="4" -->
<!-- .element: class="fragment" data-fragment-index="3" -->
----
- 單純只用作法一或作法二都會 TLE
- 作法一（枚舉兩個鄰點）碰到點度很大的點會 TLE<!-- .element: class="fragment" data-fragment-index="2" -->
- 作法二（枚舉整張圖的邊）要 $O(NM)$，一樣會 TLE<!-- .element: class="fragment" data-fragment-index="3" -->
----
那...如果把點按照度數大小分類呢？
----
- 以 $\sqrt{M}$ 為分界點
- 點度不到 $\sqrt{M}$ 稱為<!-- .element: class="fragment" data-fragment-index="1" --><span class="yellow">輕點</span><!-- .element: class="fragment" data-fragment-index="1" -->
- 點度超過 $\sqrt{M}$ 稱為<!-- .element: class="fragment" data-fragment-index="2" --><span class="yellow">重點</span><!-- .element: class="fragment" data-fragment-index="2" -->
----
- 對於輕點，我們使用作法一（$O(d_u^2)$ 枚舉兩個鄰點）
- 輕點點度不大，比較適合作法一<!-- .element: class="fragment" data-fragment-index="1" -->
- 對於重點，我們使用作法二（$O(M)$ 枚舉整張圖的邊）<!-- .element: class="fragment" data-fragment-index="2" -->
- 重點數量不會太多，比較適合作法二<!-- .element: class="fragment" data-fragment-index="3" -->
----
### 很神奇的，這樣子分 case 會是好的！
----
### 複雜度證明
這裡先提點一些重要性質<!-- .element: class="fragment" data-fragment-index="1" -->
- <span class="yellow">輕點度數不會太大，是 $O(\sqrt{M})$ 的量級</span><!-- .element: class="fragment" data-fragment-index="2" -->
- <span class="yellow">重點不會有太多個，不會超過 $O(\sqrt{M})$ 個</span><!-- .element: class="fragment" data-fragment-index="3" -->
- 邊只有 $M$ 條，所有點的度數和為 $2M$。<!-- .element: class="fragment" data-fragment-index="4" -->
- 一個重點就至少佔了 $\sqrt{M}$ 條邊<!-- .element: class="fragment" data-fragment-index="5" -->
- 所以重點個數 $\leq \frac{2M}{\sqrt{M}} = 2\sqrt{M}$。<!-- .element: class="fragment" data-fragment-index="6" -->
----
### 複雜度證明 — 輕點
- 剛剛假設我們可以快速查詢兩個點是否有邊連接，在此先設為 $O(1)$。<!-- .element: class="fragment" data-fragment-index="1" -->
- 則處理所有輕點的複雜度為 $O(\sum d_u^2)$。<!-- .element: class="fragment" data-fragment-index="2" -->
- 也就是所有輕點度數的平方和<!-- .element: class="fragment" data-fragment-index="2" -->
- $O(\sum d_u^2) = O(\sum \sqrt{M} \cdot d_u) = O(\sqrt{M} \sum d_u) = O(M \sqrt{M})$<!-- .element: class="fragment" data-fragment-index="3" -->
### 處理輕點只要 $O(M \sqrt{M})$！<!-- .element: class="fragment" data-fragment-index="4" -->
----
### 複雜度證明 — 重點
- 算一個重點的答案複雜度是 $O(M)$。<!-- .element: class="fragment" data-fragment-index="1" -->
- 重點只有 $O(\sqrt{M})$ 個<!-- .element: class="fragment" data-fragment-index="2" -->
### 處理重點一樣只要 $O(M \sqrt{M})$！<!-- .element: class="fragment" data-fragment-index="3"-->
----
總時間複雜度：$O(M \sqrt{M})$
皆大歡喜 OwO
----
總時間複雜度：$O(M \sqrt{M})$
皆大歡喜 OwO？
----
「假設我們可以快速查詢兩個點是否有邊連接」
對，現在我們來解決這個問題<!-- .element: class="fragment" data-fragment-index="1" -->
----
- 把存圖的 `vector<vector<int>>` 改成 `vector<set<int>>`
- 這樣就可以 $O(\log N)$ 查詢<!-- .element: class="fragment" data-fragment-index="1" -->
- 總複雜度會變成 $O(M \sqrt{M} \log N)$。<!-- .element: class="fragment" data-fragment-index="2" -->
----
但其實我們可以利用一些技巧，把查詢從 $O(\log N)$ 降成 $O(1)$。
----
### 更好的作法
我們現在知道，給定一個點 $u$，我們可以：
1. $O(M)$ 算出圖中有幾個包含點 $u$ 的三角形<!-- .element: class="fragment" data-fragment-index="1" -->
- 開一條 bool 陣列 adj，adj[i] 表示 $u, i$ 之間有沒有邊<!-- .element: class="fragment" data-fragment-index="3" -->
2. $O(d_u^2)$ 算出圖中有幾個包含點 $u$ 的三角形<!-- .element: class="fragment" data-fragment-index="2" -->
- 我們只在乎所有枚舉到的點對 $(x, y)$ 有多少是 true（有邊連接）<!-- .element: class="fragment" data-fragment-index="4" -->
- 因此可以離線處理，把全部詢問按照端點分類存，最後再一起做<!-- .element: class="fragment" data-fragment-index="5" -->
----
```cpp=
const int maxn = 1e5 + 2;
int n, m;
int deg[maxn]; // 每個點的度數
vector<int> g[maxn]; // 圖
vector<int> qry[maxn]; // 要離線處理的詢問
vector<pii> E; // 所有邊的集合
bitset<maxn> adj;
```
----
```cpp=
int B = sqrt(m);
long long ans = 0;
for (int u = 0; u < n; ++u) {
if (deg[u] < B) {
// 輕點枚舉兩個鄰居，把詢問存起來離線處理
for (int i = 0; i < deg[u]-1; ++i) {
for (int j = i+1; j < deg[u]; ++j) {
qry[ g[u][i] ].emplace_back( g[u][j] );
}
}
} else {
// 重點用 O(M) 做
for (auto& i : g[u]) adj[i] = true;
for (auto& e : E) if (adj[e.first] && adj[e.second]) ans++;
for (auto& i : g[u]) adj[i] = false;
}
}
// 離線處理詢問
for (int u = 0; u < n; u++) {
for (auto& i : g[u]) adj[i] = true;
for (auto& v : qry[u]) if (adj[v]) ans++;
for (auto& i : g[u]) adj[i] = false;
}
cout << ans/3 << endl;
```
---
## 重點思路整理
----
- 有些問題如果用不同的角度來看會有很多種作法
- 以 Counting Triangle 為例，可以枚舉鄰居／枚舉整張圖的邊<!-- .element: class="fragment" data-fragment-index="1" -->
- 而單純只用一種解往往會在某些情況炸掉<!-- .element: class="fragment" data-fragment-index="2" -->
- 枚舉鄰居：碰到點度很大的節點會 TLE<!-- .element: class="fragment" data-fragment-index="3" -->
- 枚舉整張圖的邊：做一次 $O(M)$ 代價太高，不能做太多次<!-- .element: class="fragment" data-fragment-index="3" -->
----
- 根號算法的手法便是設定一個臨界值，小於跟大於臨界值的情況套用不同解
- 點度小的點適合「枚舉鄰居」，因為點度夠小<!-- .element: class="fragment" data-fragment-index="1" -->
- 點度大的點適合「枚舉整張圖的邊」，因為這樣的點並不多<!-- .element: class="fragment" data-fragment-index="1" -->
- 而會稱為「根號算法」，純粹是因為最佳複雜度帶有根號（和算幾不等式有關）<!-- .element: class="fragment" data-fragment-index="2" -->
<!-- ##################################################################### -->
---
## 休息／提問／[寫題單的題目](https://hackmd.io/@penguin71630/r1Q1Ite_c)
{"metaMigratedAt":"2023-06-17T00:35:45.863Z","metaMigratedFrom":"YAML","title":"根號算法 I","breaks":true,"slideOptions":"{\"transition\":\"fade\"}","contributors":"[{\"id\":\"ac1507e0-f05c-4708-bdd2-c56d13fb0dbb\",\"add\":36586,\"del\":9449}]"}