<style> .reveal .slides { text-align: left; font-size:30px } </style> # 高維偏序問題 1. CDQ分治 2. 二維資節 - 2D BIT - 2D 線段樹 4. 持久化 - 持久化線段樹 - 樹上持久化 - 可復原並查集 - 時間線段樹 --- ## CDQ分治 ---- CDQ分治並不是演算法，而是與大部分的解法一樣只是一種想法，不過這種想法是由非常多我們已知的算法，資料結構等去組合而成的，因此非常好用。 CDQ分治可以用來解決點對問題(二維偏序問題)，加入資料結構後(BIT)也可以解決三維偏序問題，偶爾也會出現在動態規劃的優化或者是轉移式，不過並不在本次教學的主要目的當中。 *此算法是活的並不是模板 ---- ## 二維偏序 以最常見的逆序數對問題為例子，我們常見的解法就是先將第一個維度排序，接下來有以下幾種統計第二個維度的方法 : 1. merge sort 2. BIT等資料結構 而針對二維的CDQ分治，他的實作代碼會非常非常像merge sort，也是遞迴 $(l,mid)$ 和 $(mid,r)$ 去解決問題。 ---- 為什麼會說他很像是merge sort呢? 因為他對於陣列的處理方法一樣，唯一的差別就是不需要合併起來，在分割則是需要使用雙指針去求合乎需求的點對數量。 那直接看代碼應該會比較快理解。 ---- ```cpp= ll cdq(int A[], int n){ //A是陣列 n是陣列大小 if (n == 1) return 0; int mid = n >> 1, i = 0, j = mid; ll ans = cdq(A, mid) + cdq(A + mid, n - mid); sort(A, A + mid, greater<int>()), sort(A + mid, A + n, greater<int>()); for (; j < n; ++j){ while (i < mid && A[i] > A[j]) i++; //雙指針 ans += i; } return ans; } ``` 那它每層的時間複雜度為 $O(n\ lg\ n)$ 總共有 $O(lg\ n)$ 層，所以這樣的時間複雜度為 $O(n \ lg^2 n)$ ---- 為了達到可以利用雙指針，因此會需要先排序，不過根據我們之前所學，會發現我們完全可以把排序的過程移動到雙指針的掃描中。這樣子就不需要到每層 $O(n\ lg\ n)$ 的複雜度。 ```cpp= ll cdq(int A[], int n){ int B[MAXN]; //暫存數組 if (n == 1) return 0; int mid = n >> 1, i = 0, j = mid, k = 0; ll ans = cdq(A, mid) + cdq(A + mid, n - mid); for (; j < n; ++j){ while (i < mid && A[i] > A[j]) B[k++] = A[i++]; //紀錄答案且排序 ans += i, B[k++] = A[j]; } while (i < mid) B[k++] = A[i++]; //複製剩下沒用到的，這步與merge sort非常相似 memcpy(A, B, sizeof(int) * k); //把B複製回A 然後捨棄B return ans; //組數 } ``` 你就會發現它長得與merge sort 幾乎一樣，它就是復刻了merge sort中間的過程。 CDQ就是利用了merge sort的基礎，維護它的有序性質，並且再通過左右區間前一維已經排序好的性值去統計答案。 ---- ## 三維偏序 那就到重頭戲三維偏序，既然第一維可以直接用sort解決，而第二維使用到分治的想法解決，那麼第三維理所當然的就是要把第二維符合條件的pair通通壓入BIT中，然後使用正常的求逆序數對的方法求，那就沒有問題了 OuOb 相信大家都一定會使用BIT去求二維偏序，這對於打ICPC的選手算是必備技能。 ---- ```cpp= #define lowbit(x) ((x) & (-x)) void update(int i, int x){ for (; i <= MAXM; i += lowbit(i)) tree[i] += x; } int query(int n){ int ans = 0; for (; n; n -= lowbit(n)) ans += tree[n]; return ans; } int main(){ int n, x; scanf("%d", &n); for (int i = 0; i < n; ++i){ scanf("%d%*d", &x); ans[query(x + 1)]++; update(x + 1, 1); } ``` ---- 那當然，第一層使用排序是顯而易見的，但你如果第二第三層都想要使用BIT，或者是都想要使用CDQ，哪也不是不行，也就是BIT裡面包BIT 或是CDQ套CDQ，但今天就不另行補充，用法都一樣。 只要記得 CDQ分治的主要概念就是可以用來計算左區間對於右區間的貢獻，主要的經典問題有 : 逆序數對 ， 求LIS ， 離線分治等等 ---- 例題 [洛谷 P3810](https://www.luogu.com.cn/problem/P3810) 一函數$f(i)$ 表示 對 $i$ 來說有幾個 $j$ 滿足以下式子 : $\ \ j\neq i$ 且 $\ a_j\leq a_i$ 且 $\ b_j \leq b_i$ 且 $\ c_j \leq c_i$ 輸出的第 $k$ 行表示 有幾個 $i$ 其 $f(i) = k$ ($k\in 0-base$) ```txt sample input sample output (a b c) 3 3 3 2 2 3 3 1 2 3 1 0 3 1 1 1 ``` ---- ```cpp= int CDQ (int l, int r) { //此陣列使用vector<array<int, 3>> A(n);的存法 if (r - l <= 1) return; int mid = l + r >> 1; CDQ(l, mid), CDQ(mid, r); vector<int> tmp; for (int i = l, j = mid; i < mid or j < r; ) { while (i < mid and (j == r or A[ord[i]][1] <= A[ord[j]][1])) { bit.add(A[ord[i]][2], 1); tmp.push_back(ord[i]); i++; } if (j < r) { ans[ord[j]] += bit.que(A[ord[j]][2]); tmp.push_back(ord[j]); j++; } } for (int i = l; i < mid; i++) bit.add(A[ord[i]][2], -1); copy(all(tmp), ord.begin() + l); }; ``` special thanks for @warner1129 ---- 而至於BIT的部分 就是普通的BIT ```cpp= struct BIT { vector<int> v; int n; BIT(int _n) : n(_n), v(_n + 1) {} int lowbit(int x) { return x & -x; } void add(int p, int x) { for (int i = p; i <= n; i += lowbit(i)) v[i] += x; } int que(int p) { int r = 0; for (int i = p; i > 0; i -= lowbit(i)) r += v[i]; return r; } }; ``` ---- 然後只需要統計就可以了 其實與之前寫過的題目並無太大的差別 ```cpp= for (int l = 0, r = 0; l < n; l = r) { while (r < n and A[ord[l]] == A[ord[r]]) { r++; } if (r - l > 1) { for (int i = l; i < r; i++) { ans[ord[i]] = ans[ord[r - 1]]; } } } vector<int> cnt(n); for (int i = 0; i < n; i++) cnt[ans[i]]++; for (int i = 0; i < n; i++) cout << cnt[i] << '\n'; ``` 這題算是簡單的裸題 ---- [2022NCPC 決賽第 K 題](https://ncpc.ntnu.edu.tw/file/111/%E6%B1%BA%E8%B3%BD-111.pdf) 題意 : 給定三個數組求它們的LCS。  第一行為testcase 每筆測資為三個數組的長度，接下來三行為三個數組 ---- (我就是從這題學到三維偏序的 具體的做法 可以離散化 也可以使用map映射， 第 $i_a$ 為 $i$ 在 $str_a$中的index 第 $i_b$ 為 $i$ 在 $str_b$中的index 第 $i_c$ 為 $i$ 在 $str_c$中的index 然後就是裸的三維偏序題 ---- 當年的 K ，前10名的隊伍線  ---- LIS和LCS同理 :P 去用題目練習看看 https://pastecode.io/s/r4sm0opi 另外此為模板題的完整解，若對CDQ有不熟只需要抱著這個硬啃就會了 總結就是 CDQ為解決點對相關問題，計算左區間端點對右區間端點的貢獻。 --- ## 二維資料結構 - 2D BIT - 2D Segment Tree ---- ## 經典題 2D 版 給 $n\times m$ 的矩陣，$q$ 筆操作，每次為以下其中一種 1. 左上 $(l, u)$ 到右下 $(r, d)$ 的子矩陣，每個元素加值 $v$ 2. 詢問左上 $(l, u)$ 到右下 $(r, d)$ 的子矩陣總和 <br><br> - $1\le n, m\le 5000$ - $1\le q\le 10^5$ ---- 開 $n$ 顆線段樹分別維護長度為 $m$ 的區間 ? <span>$\to$ $O(q\cdot n \log m)$<br><!-- .element: class="fragment" data-fragment-index="1" --></span> <span>$\to$ $6\cdot 10^9$<br><!-- .element: class="fragment" data-fragment-index="2" --></span> <span>$\to$ TLE :\(<br><!-- .element: class="fragment" data-fragment-index="3" --></span> ---- $\to$ 2D Data Structure ! ---- ## 2D Binary Indexed Tree ---- 對於 1D BIT，第 $i$ 個位置維護的是區間 $(i-lowbit(i), i]$ 的值。 query(i) 求的是 $1\sim i$ 的前綴總和 ```cpp= ll query(int x){ ll ret = 0; while(x){ ret += bit[x]; x -= lowbit(x); } return ret; } ``` ---- ## 求出前綴總和  求出前綴區間 a[1..11] 從 11 開始， 11 儲存區間長度為 1$\to$ a[11..11] 得到 $a_{11}$，往前求出位置 10 儲存的總和 $\to$ a[9..10] 得到 $a_{[9..10]}$，往前求出位置 8 儲存的總和 $\to$ a[1..8] prefix$_{11} = a[1..8] + a[9..10] + a[11..11]$ ---- 而 2D BIT，第 (i, j) 個位置維護的是區間 (i-lowbit(i), i]$\times$ (j-lowbit(j), j] 的值 並且 query(x, y) 得到的是左上到 (x, y) 的二維前綴區間總和 ---- ## query(x, y) 透過加總 BIT[x][y] + BIT[x][y-lowbit(y)] + BIT[x][(y-lowbit(y)) - lowbit(y-lowbit(y))] +... ```cpp= ll tot = 0; while(y){ tot += BIT[x][y]; y -= lowbit(y); } cout << tot << endl; ``` 可以得到區間 (x-lowbit(x), x] $\times$ [1, y] 的區間總和 ---- ## query(x, y) 使用兩個迴圈遍歷兩個維度，不斷 -lowbit(x) 跳到下一個區間，總共 $\log^2 n$ 個區間 可以得到 $[1, x]\times [1, y]$ 的區間總和 單筆操作複雜度 $O(\log n\log m)$ ---- ```cpp= ll query(int x, int y){ ll ret = 0; for(int i = x; i; i -= lowbit(i)){ for(int j = y; j; j -= lowbit(j)){ ret += BIT[i][j]; } } return ret; } ``` ---- ## update(x, y) 同理，每次使用 +lowbit(x) 遍歷到下一個區間更新 總共 $O(\log n\log m)$ 個區間 ---- ```cpp= void update(int x, int y, int v){ for(int i = x; i <= n; i+=lowbit(i)){ for(int j = y; j <= m; j+=lowbit(j)){ BIT[i][j] += v; } } } ``` ---- 要得到區間 (l, u) ~ (r, d) 的總和， 使用排容 query(r, d) - query(r, u-1) - query(l-1, d) + query(l-1, u-1) 可以得到 ---- $O(q\cdot \log n\log m$) $\to$ $1.5\times 10^7$ ---- ## 二維線段樹 對於二維總和問題使用 2D BIT 可以做到， 但如果把詢問區間總和換成詢問區間最大值則需要換線段樹處理。 ---- 為了方便解說二維線段樹， 接下來的例子一樣使用求 2D 區間總和。 ---- ## 作法 線段樹裡再開線段樹，也就是第一層的線段樹的每個節點都是一棵線段樹 第一層放第一個維度 $r$，第二層放第二個維度 $c$ ---- 遞迴時先遞迴第一個維度 $r$(第一層線段樹)， 每次詢問/修改先遞迴到第一個維度的區間， 接著遞迴第二個維度 $c$ (第二層線段樹)，在第二層遞迴到指定的區間求解 ----  figure modify from https://usaco.guide/CPH.pdf#page=274 ---- ### 功能 - 2維區間詢問 - 單點修改 ### 函數 ```cpp void build(idx, idy, lx, ry, lx, ry); void update(idx, idy, lx, ry, lx, ry, pos, val); int query(idx, idy, lx, ry, lx, ry); ``` ### 線段樹大小 $16 \cdot N\cdot M$ ---- ## build 先遞迴第一個維度 $x$，再對於每個 $x$ 的區間， 遞迴第二層 $y$ 的區間，算出第二層每個子區間的總和 ---- ```cpp= #define cl(x) (x<<1)+1 #define cr(x) (x<<1)+2 void build_y(int idx, int idy, int lx, int rx, int ly, int ry){ if(ly == ry){ tree[idx][idy] = arr[idx][idy]; return; } int my = (ly+ry)/2; build_y(idx, cl(idy), lx, rx, ly, my); build_y(idx, cr(idy), lx, rx, my+1, ry); tree[idx][idy] = tree[idx][cl(idy)] + tree[idx][cr(idy)]; } void build_x(int idx, int lx, int rx){ if(lx != rx){ int mx = (l+r)/2; build_x(cl(idx), lx, mx); build_x(cr(idx), mx+1, rx); } build_y(idx, 0, lx, rx, 0, m-1); } ``` ---- ## query 詢問區間 $(qxl, qyl)\sim (qxr, qyr)$ 的區間和 一樣先遞迴第一個維度 $x$，遞迴到 $x$ 符合的詢問區間再遞迴 $y$ 的詢問區間 ```cpp= int query_y(int idx, int idy, int ly, int ry, int qly, int qry){ if(qly <= ly && ry <= qry){ return tree[idx][idy]; } int my = (ly+ry)/2, ret = 0; if(qy <= my) ret += query_y(idx, cl(idy), ly, my, qly, qry); if(qy > my) ret += query_y(idx, cr(idy), my+1, ry, qly, qry); return ret; } int query_x(int idx, int lx, int rx, int qlx, int qly, int qrx, int qry){ if(qlx <= lx && rx <= qrx){ return query_y(idx, 0, 0, m-1, qly, qry); } int mx = (lx + rx)/2, ret = 0; if(qlx <= mx) ret += query_x(cl(idx), lx, mx, qlx, qly, qrx, qry); if(qrx > mx) ret += query_x(cr(idx), mx+1, qrx, qlx, qly, qrx, qry); return ret; } ``` ---- ## update 更新 a[x][y] = p 所有有被遞迴到的區間都有子區間被更新 因此有遞迴到的區間都繼續遞迴下一個維度 ```cpp= void update_y(int idx, int idy, int lx, int rx, int ly, int ry, int qy, int val){ if(ly == ry){ if(lx == rx) tree[idx][idy] = val; else tree[idx][idy] = tree[cl(idx)][idy] + tree[cr(idx)][idy]; return; } int my = (ly+ry)/2; if(qy <= my) update_y(idx, cl(idy), lx, rx, ly, my, qy, val); else update_y(idx, cr(idy), lx, rx, my+1, ry, qy, val); tree[idx][idy] = tree[idx][cl(idy)] + tree[idx][cr(idy)]; } void update_x(int idx, int lx, int rx, int qx, int qy, int val){ if(lx != rx){ int mx = (lx + rx)/2; if(qx <= mx) update_x(cl(idx), lx, mx, qx, qy, val); else update_x(cr(idx), mx+1, rx, qx, qy, val); } update_y(idx, 0, lx, rx, 0, m-1, qy, val); } ``` ---- ## 2D線段樹複雜度 單筆操作 $O(\log N\log M)$ 空間複雜度 $O(16NM)$ 會發現空間複雜度非常高，因此通常第二個維度都是用動態開點去實作 以節省複雜度 ### d 維複雜度 單筆操作時間複雜度 $O(\log^dN)$ 空間複雜度 $O((4N)^d)$ ---- 對於二維的資料結構問題，如果只維護 $n$ 個一維資料結構複雜度可以過，則不需要毒瘤使用二維資節。 雖然複雜度較好，但實作較複雜容易出錯。 --- ## 可持久化資料結構 可持久化資料結構（Persistent data structure）是一種能夠在修改之後其保留歷史版本（即可以在保留原來數據的基礎上進行修改 --- 比如增添、刪除、賦值）的資料結構。這種資料結構實際上是不可變對象，因為相關操作不會直接修改被保存的數據，而是會在原版本上產生一個新分支 --wikipedia ---- - 可持久化線段樹 - 可復原並查集 --- ## 可持久化線段樹 由於引入者黃嘉泰姓名的縮寫與前中共中央總書記、國家主席胡錦濤(H.J.T.)相同，因此這種資料結構也被稱為「主席樹」 ---- ### 功能 修改值，詢問值，回復歷史版本 如以下操作 1. **單點**修改第 $i$ 格的值為 $v$ 2. 詢問區間 $[l,r]$ 的總和為多少 3. 將序列變回第 $k$ 次操作之前的版本 ---- 當有數值修改，如果每次都重新把整棵線段樹重新存一遍， 則會花費過多的空間與時間 操作 $k$ 次，則有 $k$ 個版本，複雜度為 $O(nk)$ ---- 觀察下面的圖會發現，如果修改一個點的值，最多只會更新 $\log N$ 個點 其他點不影響，所以其實如果有修改只需要儲存那 $\log N$ 個點就好 <div style="position: absolute; right: 60%; top:100%;">  </div> <div style="position: absolute; left: 57%; top:100%;">  </div> ---- 如下圖為例，一樣修改第 3 格的值，則將有變動到的節點重新存一遍，沒變動到的區間直接指向原本的地方 <div style="position: absolute; right: 60%; top:100%;">  </div> <div style="position: absolute; left: 57%; top:100%;">  </div> ---- 原本線段樹的節點使用 index 來找左右子節點， 但持久化後每個版本的節點都會不同 因此我們可以改用指標來實作 ```cpp= struct node{ ll val; node *l, *r; }; ``` ---- 而每次更新版本時，我們需要再儲存新版本的根節點位置， 方便之後回復版本時找到那棵線段樹  ```cpp= void add_ver(int x,int v){ //修改位置 x 的值為 v ver.push_back(update_ver(ver.back(), 0, n-1, x, v)); } ``` ---- ### 實作細節 可持久化結構用指標比較容易實作 ```cpp= struct node{ ll val; node *l, *r; }; vector<node *> ver; //用一個vector紀錄全部版本的根節點 void build(node *now_ver, l, r); ll query(node *now_ver, l, r, ql, qr); node *update_ver(node *pre_ver,int l,int r,int pos,int v); //回傳新建的節點 void add_ver(int x,int v){ //修改位置 x 的值為 v ver.push_back(update_ver(ver.back(), 0, n-1, x, v)); } ``` ---- ### 建新版本 ```cpp= node *update_ver(node *pre_ver, node *x, int l, int r, int pos, int v){ node *x = new node(); //當前位置建立新節點 if(l == r){ x->val = v; return x; } int mid = (l+r)>>1; if(pos <= mid){ //更新左邊 x->l = update(pre_ver->l, x->l, l, mid, pos, v); //左邊節點連向新節點 x->r = pre_ver->r; //右邊連到原本的右邊 } else{ //更新右邊 x->l = pre_ver->l; //左邊連到原本的左邊 x->r = update(pre_ver->r, x->r, mid+1, r, pos, v); //右邊節點連向新節點 } x->val = x->l->val + x->r->val; return x; } ``` ---- ### 用途 上面的舉例為裸的操作， 而持久化線段樹還有很大的用途 通常是用來解決 **兩個維度** 以上的較複雜的問題。 因此通常需要自己分析題目所需，轉換為持久化線段樹實作。 ---- ### 例題 給定長度為 $n$ 的序列 $a$， $q$ 筆詢問，每次問 **區間 [l, r]** 之間，第 **$k$** 大的數字 $1 \le n, q \le 2 \cdot 10^5$ $1 \le a_i \le 10^9$ <span>$\to$ 區間 [l, r]<!-- .element: class="fragment" data-fragment-index="1" --></span> <span>$\to$ 第 k 大<br><!-- .element: class="fragment" data-fragment-index="2" --></span> <span>兩個維度的問題 !<br><!-- .element: class="fragment" data-fragment-index="3" --></span> ---- ## 暴力的作法 每筆詢問使用 nth_element 花 O(n) 時間找第 k 大， 總複雜度 $O(nq)$ <span>會發現這個複雜度好像似曾相似? <!-- .element: class="fragment" data-fragment-index="1" --></span> <span>持久化線段樹的暴力版 O(nk)! <!-- .element: class="fragment" data-fragment-index="2" --></span> ---- 把一個其中一個維度使用持久化的概念 ! - 區間 [l, r] - 第 k 大 ---- ### 區間 [l, r] 使用持久化處理 從第一個數字開始依序加入進線段樹 每更新一個數字，當成多一個版本 線段樹內的每個節點儲存區間 [l, r] 內的數字出現數量 第 $i$ 棵線段樹儲存前綴 $i$ 個元素 ---- ### 第 k 大 要求出線段樹上第 $k$ 小的數字， 可以在線段樹上二分搜。 ```cpp= //val 儲存當前節點的數量 int query(node *x, int l, int r, int k){ if(l == r) return l; int mid = (l+r)>>1; if(x->l->val <= k) return query(x->l, l, mid, k); else return query(x->l, mid+1, r, k - x->l->val); } ``` ---- ### 區間第 k 大 而使用第 $r$ 個版本的數量 - 第 $l-1$ 個版本求出來的數量 即可求出區間 [l, r] 內第 $k$ 小的數字 ```cpp= // pre 為第 l-1 個版本, now 為第 r 個版本 int query(node *pre, node *now, int l, int r, int k){ if(l == r) return l; int mid = (l+r)>>1; int l_num = now->l->val - pre->l->val; if(k <= l_num) return query(pre->l, now->l, l, mid, k); else return query(pre->l, now->l, mid+1, r, k - l_num); } ``` ---- 由於數字範圍很大，記得要先離散化 總複雜度 $O(q\log n)$ --- ## 可復原並查集 ### DSU Rollback 可復原並查集支援以下功能 1. 查詢元素所在集合 2. 合併兩個集合 3. 回復上一步合併操作 ---- 1. 查詢元素所在集合 2. 合併兩個集合 前兩個操作就是一般的並查集 3. 回復上一步合併操作 第三個操作要如何回復? ---- ### 使用啟發式合併維護 由於路徑壓縮會破壞節點之間的關係， 因此維護並查集時只使用啟發式合併維護，不用路徑壓縮 ```cpp= int f[MXN], sz[MXN]; int find(int x){ return f[x] == x ? x : find(f[x]); } void merge(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(sz[x] > sz[y]){ sz[x] += sz[y]; f[y] = x; } else{ sz[y] += sz[x]; f[x] = y; } } ``` ---- ### 紀錄每次合併前的狀態 可以觀察到每次合併時，改變的為 sz[x], f[y] 因此記錄起來，需要回覆上一個合併操作時，直接設為原本的值即可 ```cpp= vector<tuple<int, int, int, int>> ver; void merge(int x, int y){ x = find(x); y = find(y); if(sz[x] < sz[y]) swap(x, y); ver.push_back(make_tuple(x, sz[x], y, f[y])); if(x != y){ sz[x] += sz[y]; f[y] = x; } } ``` ---- ### Undo 回覆上一個合併操作時，直接設為原本的值即可 ```cpp= void undo(){ auto [x, szx, y, fy] = ver.back(); ver.pop_back(); sz[x] = szx; f[y] = fy; } ``` ---- 由於使用啟發式合併維護並查集，複雜度為 $O(\log n)$ 而記錄版本與回復的時間複雜度為 $O(1)$ 總複雜度為 $O(q\log n)$ ---- ### 時間線段樹 穿越時空來解決動態連通性的問題 ---- ### 經典例題 --- [Dynamic Connectivity](https://cses.fi/problemset/task/2133) 給定一張 $N$ 個點的無向圖，一開始圖上有 $M$ 條邊。 現在有 $Q$ 個操作，每個操作會是以下兩種中的一種： 1. 增加一條連接著編號 $A_i$ 與編號 $B_i$ 的邊。 2. 刪除一條連接著編號 $A_i$ 與編號 $B_i$ 的邊（保證這條邊是存在的）。 每次操作完後請輸出當前的連通塊數量。 - $1 \le N, Q \le 10^5$ - $1 \le A_i, B_i \le N$ ---- 如果只有第一個操作 1. 增加一條連接著編號 $A_i$ 與編號 $B_i$ 的邊。 每次操作完後請輸出當前的連通塊數量。 ---- 使用一般並查集好好維護連通塊大小即可 ---- 如果只有第二個操作 2. 刪除一條連接著編號 $A_i$ 與編號 $B_i$ 的邊（保證這條邊是存在的）。 每次操作完後請輸出當前的連通塊數量。 ---- 先把最後的圖儲存起來 可以反著從最後一個刪除操作做回來，就變成只有加邊的問題了 ---- 而原問題...加邊/刪邊同時... <span>還是不會做 :P <!-- .element: class="fragment" data-fragment-index="1" --></span> ---- ### 時間線段數 ! 離線作法 把每條邊的生存時間當成區間儲存在線段樹上。 ---- 假設依序有 8 個事件，把每個事件當成一個時間點 1. add 1 3 2. add 2 5 3. query 3 4. remove 1 3 5. add 4 2 6. query 2 7. remove 4 2 8. add 1 2 1 3 這條邊的生存時間為時間 1~4 2 5 這條邊的生存時間為時間 2~8 4 2 這條邊的生存時間為時間 5~7 1 2 這條邊的生存時間為時間 8~8 ---- 把邊放到線段樹上 1 3(1~4), 2 5(2~8), 4 2(5~7), 1 2(8~8)  ---- 把每條邊(event) 依序加入到線段樹上儲存 ```cpp= vector<pair<int, int>> tree[MXN<<2]; void insert(int i, int l, int r, int ql, int qr, pair<int, int> event){ if(ql <= l && r <= qr){ tree[i].push_back(event); return; } int mid = (l+r)>>1; if(ql <= mid) insert(cl(i), l, mid, ql, qr, event); if(qr > mid) insert(cr(i), mid+1, r, ql, qr, event); } ``` ---- 接著只需要遍歷這顆線段樹! 每走到一個節點時，把當前節點上的邊使用並查集合併 往下遞迴子節點，走到一個詢問時儲存連通塊大小到答案中 離開當前節點時，把當前節點上的邊回復 ---- 走到最深時，判斷當前時間是否有詢問，有的話將答案儲存起來 ```cpp= void traversal(int i, int l, int r){ if(l == r){ if(query[l]) ans[query[l]] = component_num; return; } for(pair<int, int> event : tree[i]) merge(event.first, event.second); int mid = (l+r)>>1; traversal(cl(i), l, mid); traversal(cr(i), mid+1, r); for(int i = 0; i < tree[i].size(); i++) undo(); } ``` ---- ### 複雜度 - 插入一個事件進線段樹上複雜度為 $O(\log n)$ - 合併為 $O(\log n)$ - 回復為 $O(1)$ - 遍歷線段樹為 $O(n+q)$ 總複雜度 $O(q\log n)$ --- [Problem List](https://vjudge.net/contest/576254)