<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)
---
## 整體二分
怎麼變成二分了? 其實分治的過程和二分蠻像的
這個技巧可以讓我們一次二分很多東西
----
假如有很多個東西需要二分
你可以每次都從頭做
但這樣好像會有很多次重覆到的操作
----
所以我們可以用分治處理多組詢問的技巧
套用到二分上面
{"metaMigratedAt":"2023-06-16T11:48:05.766Z","metaMigratedFrom":"YAML","title":"分治初探","breaks":"true","slideOptions":"{\"theme\":\"sky\",\"transition\":\"slide\"}","contributors":"[{\"id\":\"853e1517-7034-4077-803a-7bb83a49f00a\",\"add\":8006,\"del\":310}]"}