<style>
.reveal .slides {
font: 0.65em "Fira Mono", monospace;
}
.yellow {
color: yellow;
}
.gray {
color: #c9c9c9;
}
.red {
color: #f01f45;
}
.green {
color: #2cd620;
}
</style>
# 根號算法 II
#### **Gino**
---
## 內容大綱
- ★★★★★ 操作分塊
- ★★★★☆ 綜合練習
---
今天這堂課涵蓋的主題只有操作分塊，但難度較高。
所以其他根號的主題我不打算講，今天前半堂課只 focus 在操作分塊。<!-- .element: class="fragment" data-fragment-index="1" -->
後半堂課會讓大家練一些題目，複習這堂還有上堂課提到的知識點。<!-- .element: class="fragment" data-fragment-index="2" -->
有問題都可以隨時問 :D<!-- .element: class="fragment" data-fragment-index="3" -->
---
另外考量到莫隊算法的性質，比較貼近下堂課的主題「離線演算法」。
因此莫隊算法會擺在下一堂課。<!-- .element: class="fragment" data-fragment-index="1" -->
---
<!-- #################################################### -->
## 操作分塊
----
- 之前學過對序列分塊、對值域分塊
- 但「操作」也可以分塊喔！<!-- .element: class="fragment" data-fragment-index="1" -->
----
### What is 操作分塊
- 「有 $Q$ 筆操作，每筆操作可能為**修改**或**詢問**」<!-- .element: class="fragment" data-fragment-index="1" -->
- 簡單來說就是有很多個操作<!-- .element: class="fragment" data-fragment-index="2" -->
- 把操作分組，一組一組處理<!-- .element: class="fragment" data-fragment-index="3" -->
- 這樣很神奇的可以降低複雜度<!-- .element: class="fragment" data-fragment-index="4" -->
----
### [區間修改、單點詢問](https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/E)
有一個長度為 $N$ 的序列 $\langle a_N \rangle$，你要處理 $Q$ 筆操作：
- ADD l r x：將區間 $[a_l, a_r]$ 加上 $x$
- QRY i：詢問 $a_i$ 為多少
$N, Q \leq 10^5$
----
- 把操作每 $\sqrt{Q}$ 個分成一組
- 先處理第一組操作<!-- .element: class="fragment" data-fragment-index="1" -->
- 按照時間依序處理操作<!-- .element: class="fragment" data-fragment-index="2" -->
----
- 碰到**修改**時，先不要做任何事
<!-- .element: class="fragment" data-fragment-index="1" -->
----
- 碰到**修改**時，先不要做任何事
###### 紅色標記表示這個**修改**未完成
----
- 碰到**詢問**時，暴力跑過之前的所有修改，看有沒有要加值
- 最多只會跑過 $O(\sqrt{Q})$ 個修改，所以暴力複雜度是好的<!-- .element: class="fragment" data-fragment-index="2" -->
<!-- .element: class="fragment" data-fragment-index="1" -->
----
- 重複之前的動作，直到處理完第一組的操作
----
- 接下來，我們要把這組裡面**所有的修改**一次做完
- 「做完」的定義是把要加的值加到原本的陣列上<!-- .element: class="fragment" data-fragment-index="1" -->
- 如何**一次做完**？<!-- .element: class="fragment" data-fragment-index="2" -->
### 掃描線！<!-- .element: class="fragment" data-fragment-index="3" -->
----
### 這是基礎掃描線例題
- 把所有修改左右界拆開來，之後全部丟到一個 vector
- 排序<!-- .element: class="fragment" data-fragment-index="2" -->
- $O(N)$ 掃過整個陣列並**修改**。<!-- .element: class="fragment" data-fragment-index="3" -->
----
- 第一組的所有操作處理完畢
----
- 接下來處理第二組
- 一樣依序處理每個操作<!-- .element: class="fragment" data-fragment-index="1" -->
----
- 碰到**修改**時，一樣不要做任何事
----
- 碰到**詢問**時，暴力跑過之前<span class="red">**還沒做的**</span>修改，看有沒有要加值
- 前面組別的修改已經做過了，不用理會<!-- .element: class="fragment" data-fragment-index="1" -->
- 只要跑過同一組的修改就好！<!-- .element: class="fragment" data-fragment-index="2" -->
- $O(\sqrt{Q})$<!-- .element: class="fragment" data-fragment-index="3" -->
----
- 重複之前的動作，直到處理完第二組的操作
- 接下來一樣把第二組的所有修改抓出來，做一次掃描線更新陣列<!-- .element: class="fragment" data-fragment-index="1" -->
----
### 時間複雜度
- 操作每 $O(\sqrt{Q})$ 一塊，總共有 $O(\sqrt{Q})$ 塊。<!-- .element: class="fragment" data-fragment-index="1" -->
- <span class="yellow">處理同一塊的操作時：</span><!-- .element: class="fragment" data-fragment-index="2" -->
- 修改：我們並沒有做任何事，除了最後的掃描線，因此總複雜度 $O(N)$。<!-- .element: class="fragment" data-fragment-index="3" -->
- 詢問：一次詢問 $O(\sqrt{Q})$，總共 $O(\sqrt{Q})$ 個詢問，因此總複雜度 $O(Q)$。<!-- .element: class="fragment" data-fragment-index="4" -->
- <span class="yellow">總共有 $O(\sqrt{Q})$ 塊，故總時間複雜度為 $O((N+Q)\sqrt{Q})$。</span><!-- .element: class="fragment" data-fragment-index="5" -->
----
### 操作分塊的框架
- 把操作分組（通常是每 $\sqrt{Q}$ 個一組）<!-- .element: class="fragment" data-fragment-index="1" -->
- 處理每塊的操作：<!-- .element: class="fragment" data-fragment-index="2" -->
- 對於修改，不要做任何事<!-- .element: class="fragment" data-fragment-index="3" -->
- 對於詢問，暴力跑過同塊的修改，不要跑過更之前的修改（那些修改都已經完成了）<!-- .element: class="fragment" data-fragment-index="4" -->
- 最後把同一塊的修改一起做掉，移動到下一塊，重複一樣的事情<!-- .element: class="fragment" data-fragment-index="5" -->
----
### 休息 10 分鐘／提問
----
### [Xenia and Tree](https://codeforces.com/problemset/problem/342/E)
給一個 $N$ 個節點的樹，一開始所有點都是白色的，有 $Q$ 筆操作。
1. 把一個點塗成黑色。
2. 詢問一個點到某個黑點的最短距離。
$N, Q \leq 10^5$
----
- 一樣把操作分成一塊一塊
- 處理詢問時，我們把黑點分成「在這塊操作才被塗」還有「在這塊之前就已經塗過」<!-- .element: class="fragment" data-fragment-index="1" -->
- 對於前者，我們暴力跑過這些黑點（反正數量不多）並計算黑點和詢問點的距離<!-- .element: class="fragment" data-fragment-index="2" -->
- 樹上兩點距離 $\Rightarrow$ LCA<!-- .element: class="fragment" data-fragment-index="3" -->
----
- 對於後者，假設我們有一個表格可以查答案
- 令 dis[u] 為 u 到之前那些黑點的最近距離<!-- .element: class="fragment" data-fragment-index="1" -->
- 要維護好 dis，就必須在每塊做完的時候做一次<span class="yellow">**全點對 BFS**</span><!-- .element: class="fragment" data-fragment-index="2" -->
----
### Xenia and Tree 演算法步驟
- 把操作分組<!-- .element: class="fragment" data-fragment-index="1" -->
- 處理每塊的操作：<!-- .element: class="fragment" data-fragment-index="2" -->
- 對於修改，不要做任何事<!-- .element: class="fragment" data-fragment-index="3" -->
- 對於詢問，暴力跑過同塊的修改，計算「在這塊操作才被塗」的黑點到詢問點的距離並取最小值 $\Rightarrow$ LCA。<!-- .element: class="fragment" data-fragment-index="4" -->
- 而對於「在這塊之前就已經塗過」的黑點，我們可以用 dis 查答案。<!-- .element: class="fragment" data-fragment-index="5" -->
- 最後把同一塊的修改一起做掉，也就是做一次**全點對 BFS**，接著移動到下一塊。<!-- .element: class="fragment" data-fragment-index="6" -->
----
### 時間複雜度
- 這裡的 LCA 推薦使用 Euler Tour + Sparse Table 預處理
- 這樣可以 $O(1)$ 回答兩點距離<!-- .element: class="fragment" data-fragment-index="1" -->
- 不過倍增 LCA 也可以過<!-- .element: class="fragment" data-fragment-index="2" -->
- 忘記的回去翻圖論 I（倍增 LCA）或圖論 V（Euler Tour）的簡報<!-- .element: class="fragment" data-fragment-index="3" -->
----
### 時間複雜度（Euler Tour LCA）
- 預處理 LCA 要用的 Sparse Table $O(N \log N)$。<!-- .element: class="fragment" data-fragment-index="1" -->
- 操作每 $O(B)$ 一塊，總共有 $O(\frac{Q}{B})$ 塊。<!-- .element: class="fragment" data-fragment-index="2" -->
- <span class="yellow">處理同一塊的操作時：</span><!-- .element: class="fragment" data-fragment-index="3" -->
- 修改：我們並沒有做任何事，除了最後全點對 BFS $\Rightarrow$ $O(N)$。<!-- .element: class="fragment" data-fragment-index="4" -->
- 詢問：一次詢問 $O(B)$，總共 $O(B)$ 個詢問 $\Rightarrow$ $O(B^2)$。<!-- .element: class="fragment" data-fragment-index="5" -->
- 總共 $O(\frac{Q}{B})$ 塊，故總時間複雜度為 $O(N \log N + \frac{Q}{B}(N+B^2))$。<!-- .element: class="fragment" data-fragment-index="6" -->
- $O(N \log N + \frac{NQ}{B} + QB)$。<!-- .element: class="fragment" data-fragment-index="7" -->
- <span class="yellow">取 $B = \sqrt{N}$，可得最佳複雜度 $O(N \log N + Q \sqrt{N})$。</span><!-- .element: class="fragment" data-fragment-index="8" -->
----
### 時間複雜度（倍增 LCA）
- 預處理倍增表 $O(N \log N)$。
- 操作每 $O(B)$ 一塊，總共有 $O(\frac{Q}{B})$ 塊。
- <span class="yellow">處理同一塊的操作時：</span>
- 修改：我們並沒有做任何事，除了最後全點對 BFS $\Rightarrow$ $O(N)$。
- 詢問：一次詢問 $O(B \log N)$，總共 $O(B)$ 個詢問 $\Rightarrow$ $O(B^2 \log N)$。
- 總共 $O(\frac{Q}{B})$ 塊，故總時間複雜度為 $O(N \log N + \frac{Q}{B}(N+B^2 \log N))$。
- $O(N \log N + \frac{NQ}{B} + QB \log N)$。
- <span class="yellow">取 $B = \sqrt{\frac{N}{\log N}}$，可得最佳複雜度 $O(N \log N + Q \sqrt{N \log N})$。</span>
----
Code：https://codeforces.com/contest/342/submission/159640127
----
## 休息 10 分鐘／提問
----
### [TIOJ 1171 — 我要成為海賊王](https://tioj.ck.tp.edu.tw/problems/1171)
給一個 $N$ 個節點，邊帶權的樹，一開始所有點都是白色的，有 $Q$ 筆操作。
1. 把一個點塗成黑色。
2. 詢問一個點到所有黑點的總距離。
$N \leq 10^5, \ Q \leq 10^6$
----
跟 Xenia and Tree 很像，只是題目改成：
1. 邊有權重<!-- .element: class="fragment" data-fragment-index="1" -->
2. 最短距離改成總距離<!-- .element: class="fragment" data-fragment-index="2" -->
另外，這題是重剖或樹剖的練習題，$Q$ 到 $10^6$ 是要卡掉分塊，但還是可以拿 51 分。<!-- .element: class="fragment" data-fragment-index="3" -->
----
- 一樣把操作分成一塊一塊
- 處理詢問時，我們把黑點分成「在這塊操作才被塗」還有「在這塊之前就已經塗過」<!-- .element: class="fragment" data-fragment-index="1" -->
- 對於前者，我們暴力跑過這些黑點（反正數量不多）並計算黑點和詢問點的距離<!-- .element: class="fragment" data-fragment-index="2" -->
- 樹上兩點距離 $\Rightarrow$ LCA<!-- .element: class="fragment" data-fragment-index="3" -->
----
- 對於後者，假設我們有一個表格可以查答案
- 令 dp[u] 為 u 到之前那些黑點的總距離<!-- .element: class="fragment" data-fragment-index="1" -->
- 要維護好 dp，就必須在每塊做完的時候做一次<!-- .element: class="fragment" data-fragment-index="2" --><span class="yellow">**全方位木 DP**</span><!-- .element: class="fragment" data-fragment-index="2" -->
----
### TIOJ 1171 演算法步驟
- 把操作分組<!-- .element: class="fragment" data-fragment-index="1" -->
- 處理每塊的操作：<!-- .element: class="fragment" data-fragment-index="2" -->
- 對於修改，不要做任何事<!-- .element: class="fragment" data-fragment-index="3" -->
- 對於詢問，暴力跑過同塊的修改，計算「在這塊操作才被塗」的黑點到詢問點的距離並取最小值 $\Rightarrow$ LCA<!-- .element: class="fragment" data-fragment-index="4" -->
- 而對於「在這塊之前就已經塗過」的黑點，我們可以用 dp 表查答案。<!-- .element: class="fragment" data-fragment-index="5" -->
- 最後把同一塊的修改一起做掉，也就是做一次**全方位木 DP**，接著移動到下一塊。<!-- .element: class="fragment" data-fragment-index="6" -->
----
### 時間複雜度
跟剛剛的 Xenia and Tree 一樣，複雜度為 $O(N \log N + Q \sqrt{N})$ 或是 $O(N \log N + Q \sqrt{N \log N})$。
這裡就不再贅述。
----
### 關於常數
這題時限很緊，加了一些常數優化才拿到 51 分：
1. 預先紀錄好全方位木 DP 的轉移順序，這樣可以避免遞迴的常數。
2. 塊的大小為動態調整。
----
### 關於常數
有些人可能知道「鍊式前向星」這個常數優化方法，但對這題來說優化不大。
有興趣的可以自行搜尋、爬文，這裡不贅述。
----
Code
```cpp=
const int maxn = 1e5 + 5;
const int maxq = 1e6 + 5;
vector<pair<int, ll> > g[maxn];
int n, q;
bitset<maxn> col;
ll dep[maxn];
int in[maxn], stp = 1;
int lg[maxn*2];
ll tour[maxn*2];
ll spt[18][maxn*2];
vector<int> leaf;
int tr1[maxn], tr2[maxn], tr1ptr, tr2ptr;
ll dp[maxn];
int sub[maxn];
int mod[maxn], mid[maxn];
int qry[maxq], qid[maxq];
void dfs(int u, ll curdep) {
dep[u] = curdep;
in[u] = stp;
tour[stp++] = curdep;
if (!g[u].empty()) tr2[tr2ptr++] = u;
Each(e, g[u]) {
int v = e.F; ll w = e.S;
dfs(v, curdep+w);
tour[stp++] = curdep;
}
if (g[u].empty()) leaf.emplace_back(u);
else tr1[tr1ptr++] = u;
}
void init() {
cin >> n >> q;
col.reset();
REP(i, n-1) {
int u, v; ll w;
cin >> u >> v >> w; u++, v++;
g[u].emplace_back(mp(v, w));
}
for (int cnt = 0; cnt < 18; cnt++) {
for (int i = (1<<cnt); i < (1<<(cnt+1)); i++) {
if (i >= maxn*2) break;
lg[i] = cnt;
}
}
dfs(1, 0);
for (int i = 1; i < stp; i++) {
spt[0][i] = tour[i];
}
for (int k = 1; k < 18; k++) {
for (int i = 1; i+(1<<k)-1 < stp; i++) {
spt[k][i] = min(spt[k-1][i], spt[k-1][i+(1<<(k-1))]);
}
}
}
void buildDis() {
// do rerooting DP
Each(u, leaf) sub[u] = col[u], dp[u] = 0;
int u, v; ll w;
REP(i, tr1ptr) {
u = tr1[i];
sub[u] = col[u];
dp[u] = 0;
Each(e, g[u]) {
v = e.F, w = e.S;
sub[u] += sub[v];
dp[u] += dp[v] + w * sub[v];
}
}
REP(i, tr2ptr) {
u = tr2[i];
Each(e, g[u]) {
v = e.F, w = e.S;
dp[v] += dp[u] - (dp[v] + w*sub[v]) + w * (sub[1]-sub[v]);
}
}
}
void solve() {
bool needBuild = false;
int qcnt = 0, modptr, qryptr;
int op, u, v, uid, l, r, len, k;
ll ans;
while (qcnt < q) {
if (needBuild) buildDis();
modptr = 0;
qryptr = 0;
ll ctrl = 0;
while (ctrl <= 97000) {
if (qcnt >= q) break;
cin >> op >> u; u++;
qcnt++;
if (op == 1) {
if (!col[u]) {
mod[modptr] = u;
mid[modptr] = qcnt;
modptr++;
col[u] = true;
}
} else if (op == 2) {
qry[qryptr] = u;
qid[qryptr] = qcnt;
qryptr++;
ctrl += modptr;
}
}
REP(i, qryptr) {
u = qry[i], uid = qid[i];
ans = dp[u];
REP(j, modptr) {
v = mod[j];
if (mid[j] > uid) break;
l = in[u], r = in[v];
if (l > r) swap(l, r);
len = r-l+1;
k = lg[len];
ans += dep[u] + dep[v] - 2 * min(spt[k][l], spt[k][r-(1<<k)+1]);
}
cout << ans << endl;
}
needBuild = modptr > 0;
}
}
```
---
## 綜合練習
----
### [Lena and Queries](https://codeforces.com/contest/678/problem/F)
有一個集合，一開始為空，接下來有 $Q$ 筆操作：
1. 加入一個線型函數 $f(x) = ax + b$ 到集合裡。
2. 拔掉一個線型函數。
3. 給定 $x$，詢問 $f(x)$ 的最大值。
$1 \leq Q \leq 3 \times 10^5$
----
### [NEOJ 741 橋梁](https://neoj.sprout.tw/problem/741/)
給一張 $N$ 點 $M$ 邊的帶權圖，接下來有 $Q$ 筆操作：
1. 修改一條邊的權重
2. 給定 s, w，求從 s 出發，在「只能經過邊權不超過 w 的邊」的情況下，能走到多少個點？
$N \leq 5 \times 10^4, \ M, Q \leq 10^5$
----
### [Serega and Fun](https://codeforces.com/contest/455/problem/D)
### [Strange Queries](https://codeforces.com/gym/101138/problem/D)
### [NEOJ 小咲的玩具](https://neoj.sprout.tw/problem/722/)
{"metaMigratedAt":"2023-06-17T02:20:34.926Z","metaMigratedFrom":"YAML","title":"根號算法 II","breaks":true,"slideOptions":"{\"transition\":\"fade\"}","description":"★★★★★ 操作分塊","contributors":"[{\"id\":\"ac1507e0-f05c-4708-bdd2-c56d13fb0dbb\",\"add\":14170,\"del\":754}]"}