<style> body{ background-attachment: fixed; background-repeat: no-repeat; background: -webkit-linear-gradient(left, #ffffff,rgba(51,51,51,0.3)), url("https://i.imgur.com/wuYV61U.jpg") center no-repeat fixed; }; </style> <font color="black"> <font size=15><b> 分治初探 </b></font> <font size=6><b> 作者: LittlePants </b></font> ---- ## 你會分治嗎? https://gilbert12-tw.gitbook.io/littlepants_cp_note/cp-practice/untitled ---- 分治是個很常聽到的主題 但如果問你有哪些題目一定要使用到分治 可能會很難回答出來 ---- 因為分治其實是一種想法、思考方式 但也因此往往可以使用砸資料結構省去這一層思考 ---- 分治的英文是 divide and conquer 也就是把他分開來然後解決掉，分治真的是一個很精闢的翻譯 也就是說，我們把原本的問題切成小塊解決各自解決，最後不要忘了再計算合併起來的答案 ---- 通常分治可以把$O(N^2)$的複雜度降到$O(NlogN)$ 只要好好考慮如何分開和合併通常就能解決問題了 ---- 線段樹其實也是一個活用分治的例子 我們接下來講解一些分治的有趣應用 --- ## 分治解決離線區間詢問 ---- 我們直接來看個例題 ---- ### [靜態RMQ](https://cses.fi/problemset/task/1647) **題目大意** : 查詢數列中 $q$ 個連續區間的最小值 ---- 這題可以用分治做??? 不是套個 Sparse Table 或 Segment Tree 就解決了嗎? ---- 沒錯 資料結構能輕鬆地解決這題 但我們現在用分治的想法來做 ---- 首先我們先對 $[1, n]$ 這整個區間分治 ---- ### 思考 我們應該甚麼時候處理詢問?? ---- 分裂的時候好像不太合理 所以應該是合併的時候處理 ---- 如果我們現在要查詢多個 $[ql, qr]$ 區間 且現在我們分治到了 $[l, r]$ 這個區間 我們可以先理出 $l \leftarrow mid$ 和 $mid + 1 \rightarrow r$ 的前、後綴最小值 如果遇到了橫跨 $mid$ 兩邊的詢問就很好解決了 ---- 但如果我們分治到每個區間之後 都把所有詢問便利一遍 複雜度變成 $O(N log N + qn)$ 比暴力還爛QQ ---- ### 優化 其實可以把詢問分成3類 1. 現在可以處理的詢問 2. 完全在 $mid$ 左邊的詢問 3. 完全在 $mid$ 右邊的詢問 ---- 第1種可以當場處理掉 第2種可以在往左邊遞迴時處理掉 第3種可以在往右邊遞迴時處理掉 ---- ## 性質 分治處理到區間$[l, r]$時 只需要處理在$[l, r]$區間內的詢問 每筆詢問都一定會當一次第一類詢問 也就是說每筆詢問都會備處理到一次 ---- 這樣感覺好多了 複雜度變如何? ---- ### 複雜度 $O((Q+N) log N)$ 證明其實不難想到 大家可以自己試試 ::: spoiler 證明 每一深度中 一個詢問最多出現一次 而總共 log N 層 ::: ---- **實作(離線)** ```cpp= void dc(int l, int r, vector<int> &qry) { if (l == r) { for (int i : qry) ans[i] = a[l]; return; } // 欲處理前、後綴最小值 int mid = (l + r) >> 1; lmn[mid] = a[mid]; rmn[mid + 1] = a[mid + 1]; for (int i = mid - 1; i >= l; i--) lmn[i] = min(lmn[i + 1], a[i]); for (int i = mid + 2; i <= r; i++) rmn[i] = min(rmn[i - 1], a[i]); // 處理詢問 vector<int> lq, rq; for (int i : qry) { if (L[i] <= mid and mid < R[i]) ans[i] = min(lmn[L[i]], rmn[R[i]]); else if (R[i] <= mid) lq.eb(i); else rq.eb(i); } dc(l, mid, lq); dc(mid+1, r, rq); } ``` ---- ### 可不可以在線? ---- 可以 只要把前、後綴最小值像ST表一樣存起來就好 空間複雜度 $O(NlogN)$ ---- 因為我們還必須要知道 一個詢問 $[a, b]$ 第一次被分在兩邊是在第幾層 暴力遞迴找的話 查詢複雜度退化成$O(log N)$ 所以可以用點位元小技巧 ---- 首先我們要先開一個陣列，這邊稱它為 $mask[]$ 我們可以對於第 $level$ 層 ， 我們把 $mask[i] (i \in [l, mid])$ 都加上 $2^{level}$ 對於一個詢問 ，我們要找到 $a$ 和 $b$ 第一次分在兩邊是第幾層。 不難發現它等價於找到 $mask[a]$ ^ $mask[b]$ 在二進位中有幾個**前導0**，所以我們就能使用 `builtin_ctz` 來達到 $O(1)$ 查詢 ---- ## 實作(在線) ```cpp= void dc(int l, int r, int dep) { if (l == r) return; int mid = (l + r) >> 1; lmn[mid][dep] = a[mid]; rmn[mid + 1][dep] = a[mid + 1]; mask[mid + 1] ^= (1<<dep); for (int i = mid - 1; i >= l; i--) lmn[i][dep] = min(lmn[i + 1][dep], a[i]); for (int i = mid + 2; i <= r; i++) rmn[i][dep] = min(rmn[i - 1][dep], a[i]), mask[i] ^= (1<<dep); dc(l, mid, dep + 1); dc(mid+1, r, dep + 1); } signed main() { IO; cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i]; dc(1, n, 0); while (q--) { int l, r; cin >> l >> r; if (l == r) cout << a[l] << '\n'; else { int t = __builtin_ctz(mask[l] ^ mask[r]); cout << min(lmn[l][t], rmn[r][t]) << '\n'; } } } ``` --- ## [例題 Mystery DAG](https://dmoj.ca/problem/dmopc21c1p3) ---- ### 題目大意 是一道互動題，$N$個點$M$條邊的有向圖，但你不知道邊的方向，你要透過查詢來得知每條邊的方向。 一次查詢可以給出兩個點集 $A$ 和 $B$，如果有邊從 $A$ 指向 $B$，系統就會回傳該邊編號給你。 ---- 但查詢是有限制的 所有查詢的 $|A| + |B|$ 不能超過 $3000$ ($|A|$表示$A$集合元素個數) 最後請你改變一些邊的方向使得這張圖沒有環( 任一種方法皆可) $2 \le N \le 300, \ 1 \le M \le \frac{N(N-1)}{2}$ ---- 首先我們可以先處理要怎麼把邊定向，使得圖是一張，應該有蠻多做法的，但我當初選了一個比較難寫的作法QQ。 可以看這題 [Acyclic Graph Edges](https://cses.fi/problemset/task/1756) ---- ### 方法1 在無向圖上做 $DFS$ ，先把邊都順著 $DFS$ 的拜訪順序定向，但如果這條邊通往已經走過的點，就把這條邊反向。 這可以用 $DFS$ 樹來解釋，不懂的話可以去查一下。 我們只要把反向邊(back edge)，都往下指，這樣就一定不會有環了。 ---- ### 方法2 每條邊都從編號小的點指向編號大的點 ---- 解決這個問題之後 要怎麼查詢才是重點 這題的詢問方式和限制比較奇特 但限制是 $3000$ 是點數的 $10$ 倍 合理猜測詢問的次數是 $O(NlogN)$ 級別 ---- 現在我們可以用到上面所提到的分治性質 如果有一條邊連接 $a, b \ (a \le b)$ 把它當成區間詢問來處理 ---- 然後我們查詢的方式就只要 每次把 $[l, mid]$ 當 $A$ 集合 $[mid+1, r]$ 當 $B$ 集合 就可以用 $O(NlogN)$ 次詢問解決這題了 ---- ### 注意 由於邊數是$O(N^2)$級別 所以總時間複雜度會是 $O(N^2logN)$ --- ## CDQ 分治 ---- 它和一般分治最大的不同在於，一般分治的題目只討論左區間$[l,mid]$, $[mid+1,r]$右區間和他們合併的答案 但CDQ分治時還可以處理左區間會影響右區間的狀況 ---- 和上面提到的分治處理區間詢問的方法其實有點類似 如果一個位置 $i$ 會對一個 $j$ 造成影響 我們只在遞迴到區間 $[l, r]$ 且 $i, j$ 橫跨 $mid$ 時處理 ---- 這樣不但能確保每個 pair 的貢獻都能被算到一次 複雜度也不會太差 ---- CDQ分治最基本的應用 就是處理多維偏序問題 我們都會用資料結構（通常是BIT）來處理二維偏序 CDQ分治可以將三維偏序降低成二維讓我們更好處理 ---- ## [例題 三維偏序](https://zerojudge.tw/ShowProblem?problemid=c571) ---- ### 題目大意 給你 $n$ 個三維空間中的點 $(x_i, y_i, z_i)$ 要你對於每個點 $i$ 求出有多少點 $j$ 滿足 $i \ne j, \ x_j > x_i, \ y_j > y_i, \ z_j > z_i$ ---- ## 資結作法 我們可以先按照 $x$ 座標排序 然後使用二維資料結構 e.g. (二維動態開點段樹 or `std map` + 二維bit) 然後就可直接掃過去了，理論時間複雜度 $O(N \log^2 {N})$ 空間複雜度 $O(N \log N)$ 但二維資料結構的常數都極為肥大且非常噁心 ---- ## CDQ 分治的作法 我們可以使用cdq分治，把題目維度下降一維，變成我們會做的東 ---- 首先先按照 $x$ 座標排序，接著開始分治。 ---- 假設現在遞迴到區間 $[l, r]$ 在遞迴處理完 $[l, mid]$, $[mid+1, r]$後 我們會需要想辦法處理 $[l, mid]$ 對 $[mid+1, r]$ 的貢獻 ---- 由於我們已經按照 $x$ 座標排序，左區間的 $x$ 一定 $\le$ 右區間的 $x$ 仿照二維偏序的作法，我們再將 $y$ 座標排序，把 $z$ 丟到資料結構裡維護。 具體來說就是邊做 merge sort 邊用 bit 維護 ---- 這個時候左邊區間的點只需要進行加值 右區間的點只需要進行查詢 ---- 最後記得每次要把用完的 BIT 清空 這樣就做完了 時間複雜度 $O(Nlog^2N)$ ---- ### 參考程式碼 ```cpp! #include<bits/stdc++.h> #define pb push_back #define eb emplace_back #define push emplace #define sz(x) (int)(x.size()) #define all(x) x.begin(), x.end() #define int long long #define pii pair<int, int> #define inf 1e9 #define INF 1e18 #define mod 1000000007 #define F first #define S second #define IO ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; void trace_() {cerr << "\n";} template<typename T1, typename... T2> void trace_(T1 t1, T2... t2) {cerr << ' ' << t1; trace_(t2...); } #define trace(...) cerr << "[" << #__VA_ARGS__ << "] :", trace_(__VA_ARGS__); const int mxN = 1e5 + 5; int n, tmp[mxN], a[mxN], x[mxN], y[mxN], z[mxN], ans[mxN], mx; struct BIT{ int b[mxN]; inline int qry(int i) { int res = 0; for (; i <= n; i += (i&-i)) res += b[i]; return res; } inline void upd(int i, int v) { for (; i > 0; i -= (i&-i)) b[i] += v; } } bit, tb; void cdq(int l, int r) { if (l == r) return; int mid = (l + r) >> 1; cdq(l, mid); cdq(mid + 1, r); int tp = l, i = l, j = mid + 1; for (; j <= r; j++) { while (i <= mid and y[a[i]] > y[a[j]]) bit.upd(z[a[i]], 1), tmp[tp++] = a[i++]; ans[a[j]] += bit.qry(z[a[j]] + 1), tmp[tp++] = a[j]; } for (int k = l; k <= mid; k++) { if(k < i) bit.upd(z[a[k]], -1); else tmp[tp++] = a[k]; } for (int i = l; i <= r; i++) a[i] = tmp[i]; } signed main() { IO; cin >> n; for (int i = 0; i < n; i++) { cin >> x[i] >> y[i] >> z[i]; a[i] = i; } sort(a, a + n, [&](int i, int j) { if (x[i] == x[j] and y[i] == y[j]) return z[i] < z[j]; if (x[i] == x[j]) return y[i] < y[j]; return x[i] > x[j]; }); cdq(0, n - 1); for (int i = 0; i < n; i++) cout << ans[i] << '\n'; } ``` ---- ### 更多例題 #### [BOI2007 Mokia](https://www.luogu.com.cn/problem/P4390) #### [Inserction of Permutaions](https://codeforces.com/contest/1093/problem/E?f0a28=1) --- ## 整體二分 怎麼變成二分了? 其實分治的過程和二分蠻像的 這個技巧可以讓我們一次二分很多東西 ---- 假如有很多個東西需要二分 你可以每次都從頭做 但這樣好像會有很多次重覆到的操作 ---- 所以我們可以用分治處理多組詢問的技巧 套用到二分上面