# 分治法
`第13週社課`

顧名思義，分而治之
分治法最核心的思想就是把大問題分割成小問題，小的問題解決之後再來組合出大的問題的答案

### 簡單的小例子：Merge Sort

merge sort 是一個分治法的經典例子，他把大區間分成小區間，小區間排序好之後再用排序好的小區間湊出大區間
:::spoiler code

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_N = 10005;

int a[MAX_N], tmp[MAX_N];

void MGS(int L, int R) {
	if (L == R) return;
	int M = (L + R) >> 1, i = L, j = M + 1, k = L;
	MGS(L, M); MGS(M + 1, R);
	while (i <= M && j <= R) {
		if (a[i] > a[j]) tmp[k++] = a[j++];
		else tmp[k++] = a[i++];
	}
	while (i <= M) tmp[k++] = a[i++];
	while (j <= R) tmp[k++] = a[j++];
	for (i = L; i <= R; ++i) a[i] = tmp[i];
}

int main() {
	int n, i;
	scanf("%d", &n);
	for (i = 0; i < n; ++i) scanf("%d", a + i);
	MGS(0, n - 1);
	for (i = 0; i < n; ++i) printf("%d ", a[i]);
}

執行結果
實際上 merge sort 還可以套進很多題目裡面當作製造單調性的解題手段(相容性很高)
:::

### 好玩的演算法：Karatsuba

這是一個把多項式乘法從$O(n^2)$變成$O(n^{1.5})$的演算法

:::spoiler explain

考慮：
$$
\left\{
\begin{aligned}
\large{f(x)=x^n\Big(f_1(x)\Big)+f_2(x)} \\
\large{g(x)=x^n\Big(g_1(x)\Big)+g_2(x)}
\end{aligned}
\right.
$$
$$\large{
\Rightarrow f(x)g(x)=
x^{2n}\Big (f_1(x)g_1(x) \Big)+
x ^ n \Big (f_1(x)g_2(x)+f_2(x)g_1(x)\Big) +
\Big (f_2(x)g_2(x)}\Big )$$
你可以用求出$\large\Big(f_1(x)+f_2(x)\Big)\Big(g_1(x)+g_2(x)\Big)$、$\large \Big(f_1(x)g_1(x)\Big)$、$\large \Big(f_2(x)g_2(x)\Big)$組合出上面你需要的東西，遞迴下去就解了

:::

:::spoiler code

這隻code其實是之前寫的，品質不太好而且可能有bug

#include <bits/stdc++.h>
#include <cmath>
using namespace std;
// からつば algorithm
float log_2 (float a) {return log(a) / log(2);}
int power (int a, int b) {for (int i = 0;i < b;i++) {a *= 2;} return a;}
void debug_vec(vector<int> a) {for (int i = 0;i < a.size();i++) {cout << a[i] << ' ';}}
vector<int> add_up(vector<int> a, vector<int> b) {
	for (int i = 0;i < a.size();i++) a[i] += b[i];
	return a;
}
vector<int> minus_up(vector<int> a, vector<int> b) {
	for (int i = 0;i < a.size();i++) a[i] -= b[i];
	return a;
}
vector<int> merge_up(vector<int> a, vector<int> b) {
	for (int i = 0;i < b.size();i++) a.push_back(b[i]);
	return a;
}
vector<int> times(vector<int> a, int t) {
	for (int i = 0;i < a.size();i++) a[i] *= t;
	return a;
}
vector<int> karatsuba(vector<int> f, vector<int> g) {
	int half_f = f.size() / 2, half_g = g.size() / 2;
	if (half_f == 1) {
		vector<int> q = {
			f[0] * g[0], f[0] * g[1] + f[1] * g[0], f[0] * g[0]
		};
		return q;
	}
	if (half_f == 2) {
		vector<int> q = {
			0,
			f[0] * g[0],
			f[0] * g[1] + f[1] * g[0],
			f[1] * g[1] + f[0] * g[2] + f[2] * g[0],
			f[0] * g[3] + f[3] * g[0] + f[1] * g[2] + f[2] * g[1],
			f[1] * g[3] + f[3] * g[1] + f[2] * g[2],
			f[2] * g[3] + f[3] * g[2],
			f[3] * g[3]
		};
		return q;
	}
	vector<int> a(f.begin(), f.begin() + half_f), b(f.begin() + half_f, f.end()),
		c(g.begin(), g.begin() + half_g), d(g.begin() + half_g, g.end());
	vector<int> p = karatsuba(add_up(a, b), add_up(c, d));
	f = karatsuba(a, c);
	g = karatsuba(b, d);
	p = minus_up(p, add_up(f, g));
	int i;
	for (i = 0;i < half_f;i++) f[half_f + i] += p[i];
	for (i = 0;i < half_f;i++) g[i] += p[half_f + i];
	return merge_up(f, g);
}

int main() {
	// int i, j, m, n, p, q;
	// scanf("%d%d", &m, &n)
	// p = power(2, log_2(m + n - 0.5));
	// vector<int> A(p, 0), B(p, 0);
	// for (i = m - 1;i > ;)
	vector<int> result = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
	vector<int>A = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1};
	vector<int>B = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, -1};
	auto C = [](int a, int b) {
		long long sum = 1;
		for (int i = 0;i < b;i++) sum *= a - i;
		for (int i = 2;i <= b;i++) sum /= i;
		return sum;
	};
	for (int i = 0;i <= 7;i++) {
		result = add_up(result, times(A, C(8, i + 1)));
		debug_vec(A);cout << endl;
		A = karatsuba(A, B);
	}
	debug_vec(result);
	return 0;
}
// 64 96 115 107 102 110 180 167 95 72 91 68 25 4 0

:::

### 平面最近點對

分左邊和右邊，用左右最小距離合併問題(把中線左右D的點做距離)

:::spoiler code

struct point{
  long long x[3];  
};

bool cmp_x(point a, point b) {
    return a.x[0] < b.x[0];
}

bool cmp_y(point a, point b) {
    return a.x[1] < b.x[1];
}

bool cmp_x_y(point a, point b) {
    if (a.x[0] < b.x[0]) {
        return true;
    } else {
        if (a.x[0] == b.x[0]) {
            return a.x[1] < b.x[1];
        } else {
            return false;
        }
    }
}

inline long long dist_2(point a, point b) {
    long long dif_x = a.x[0] - b.x[0];
    long long dif_y = a.x[1] - b.x[1];
    return (dif_x * dif_x + dif_y * dif_y);
}

pair<point, point> closest_pair_rec(point *Px, int low, int high) {
    pair<point, point> result;

    if (high - low + 1 <= 3) {
        if (n == 2) {
            result.first = Px[low];
            result.second = Px[low + 1];
        } else {
            if (dist_2(Px[low], Px[low + 1]) < dist_2(Px[low + 1], Px[low + 2])) {
                result.first = Px[low];
                result.second = Px[low + 1];
            } else {
                result.first = Px[low + 1];
                result.second = Px[low + 2];
            }
        }

        return result;
    }

    int mid = (low + high) / 2;

    pair<point, point> p1 = closest_pair_rec(Px, low, mid);
    pair<point, point> p2 = closest_pair_rec(Px, mid + 1, high);

    long long d_min = min(dist_2(p1.first, p1.second), dist_2(p2.first, p2.second));
    long long x_mid = Px[mid].x[0];

    auto *Sy = new point[high - low + 1];
    int w = 0;
    for (int i = low; i <= high; ++i) {
        if ((Px[i].x[0] - x_mid) * (Px[i].x[0] - x_mid) <= d_min) {
            Sy[w++] = Px[i];
        }
    }
    
    sort(Sy, Sy + w, cmp_y);

    pair<point, point> p3;
    bool isInMid = false;
    for (int i = 0; i < w - 1; ++i) {
        for (int j = i + 1; j < w; ++j) {
            if (dist_2(Sy[i], Sy[j]) < d_min) {
                long long d_new = dist_2(Sy[i], Sy[j]);
                if (d_new < d_min) {
                    d_min = d_new;

                    if(Sy[i].x[0] < Sy[j].x[0]){
                        p3.first = Sy[i];
                        p3.second = Sy[j];
                    } else{
                        p3.first = Sy[j];
                        p3.second = Sy[i];
                    }

                    isInMid = true;
                }
            }
        }
    }

    delete[] Sy;

    if (isInMid) {
        return p3;
    } else {
        if (d_min == dist_2(p1.first, p1.second)) {
            return p1;
        } else {
            return p2;
        }
    }
}

pair<point, point> two_d(point *set) {
    sort(set, set + n, cmp_x_y);
    auto *Px = new point[n];
    for (int i = 0; i < n; ++i) {
        Px[i] = set[i];
    }

    pair<point, point> result = closest_pair_rec(Px, 0, n - 1);

    delete[] Px;

    return result;
}

:::

### 常數優化

對於一個分治的遞迴，在小case可以換成暴力解法，會比遞迴下去更優
舉例：在計算最近點對時，如果遞迴到$n\leq 8$時，可以直接$O(n^2)$計算($n$代表有幾個點)
實作上設定一個遞迴下界，用評測系統對下界三分搜(因為他是U型函數)