# Divide & Conquer

## Intro

>Divide and conquer 基本上分成三個部分，divide、conquer 以及 combine，divide 指的是將整個問題切小，但必須確保問題的題型是一樣的；完成之後再將每個小部分都以遞迴（recursive）的方式處理，這就是 conquer，最後再把每個小部分都結合起來（combine），即是最終答案。

[抄的](https://yalanin.medium.com/%E6%BC%94%E7%AE%97%E6%B3%95-%E5%88%86%E6%B2%BB%E6%B3%95-divide-and-conquer-592145d72699)

## 快速冪

就是很快地算 $a^b$ 的值

* 如果 $b$ 等於零，$a^b=1$
* 如果 $b$ 是偶數，$a^b=a^{\frac{b}{2}}\times a^{\frac{b}{2}}$
* 如果 $b$ 是奇數，$a^b=a^{b-1}\times a$

就這樣，非常簡單

* divide：把 $b$ 除以 $2$
* conquer：遞迴計算 $a^{\frac{b}{2}}$
* combine：$a^{\frac{b}{2}}\times a^{\frac{b}{2}}$

int powButFaster(int a, int b)
{
    if (b == 0)
        return 1;
    if (b % 2 == 0)
    {
        int temp = powButFaster(a, b / 2);
        return temp * temp;
    }
    else
    {
        return powButFaster(a, b - 1) * a;
    }
}

## merge sort

首先要先思考一件事，將兩個已經排序好的陣列合併成一個排序好的陣列
所需的時間複雜度是多少？
很明顯是 $\mathcal{O}(n)$，因為只要每次都比較兩個陣列的第一項，把比較小的放進新的陣列，然後不斷重複就好。

int n;
vector<int> a(n), b(n);
vector<int> result;

...
    
int ptra = 0, ptrb = 0;

while (ptra != n || ptrb != n)
{
    int tmp = 1e9;
    if (ptra != n)
    {
        if (ptrb != n)
        {
            if (a[ptra] < b[ptrb])
            {
                result.push_back(a[ptra]);
                ptra++;
            } 
            else
            {
                result.push_back(b[ptrb]);
                ptrb++;
            }
        }
        else
        {
            result.push_back(a[ptra]);
            ptra++;
        }
    }
    else
    {
        result.push_back(b[ptrb]);
        ptrb++;
    }
}

知道了可以把一個陣列拆成兩半，各自排序好之後再合併回來之後，
我們又發現，只有一個元素的陣列本身就是排序好的。

根據以上的特性，總結出一個排序方法：

1. 將陣列不斷拆成兩半並往下遞迴，直到大小 $=1$
2. 將兩個已排序好的陣列合併

這樣就能得到一個 $\mathcal O(n\log n)$ 的排序演算法：merge sort


每一次 merge $\mathcal O(n)\times$ 一共 $\log n$ 次
所以是 $\mathcal O(n \log n)$

## 逆序數對

定義：在一個數列 $a_1,\ a_2,\ \dots,\ a_n$ 中，若有一對 $(i,\ j)$ 滿足 $i<j$ 且 $a_i>a_j$，則稱其為一對逆序數對。

給定 $a_1,\ a_2,\ \dots,\ a_n$，求有幾對逆序數對？

用 Divide & Conquer 的想法來解：
首先將區間拆成兩半，這個區間包含的逆序數對就會被分成三類：

1. $(i,\ j)$ 都在左邊
2. $(i,\ j)$ 都在右邊
3. $(i,\ j)$ 一個在左邊，一個在右邊

只要把這三個加起來，就能得到想要的答案
其中第一種和第二種只要往下遞迴就能解決，所以來看怎麼算第三種

現在數列被切成左半邊和右半邊，而 $(i,\ j)$ 一個在左邊，一個在右邊
所以對於左半邊的每一項 $a_l$，只需要算右邊有幾個 $a_r<a_l$，再把總數加總就好
具體要怎麼做？

如果左右兩邊的陣列都是已經排序好的

左邊的陣列 $l_1,\ l_2,\ \dots,\ l_n$
右邊的陣列 $r_1,\ r_2,\ \dots,\ r_n$

先思考 $l_1$ 要怎麼算
可以將 $r$ 從前往後遍歷，直到 $r_i<l_1$ 不再成立，也就是 $r_1\le r_2\le \dots\le l_1\le r_i$，
這個位置 $i$ 的值 $-1$ 就是 $l_1$ 的答案
$l_1$ 算完了，再來要算 $l_2$
這時候發現因為 $l_1\le l_2$，所以 $r_1,\ r_2,\ \dots,\ r_{i-1}$ 也一定都 $\le l_2$，所以只要從 $i$ 繼續往後比較就好。

處理完之後，怎麼才能保證左右都是排序好的陣列？
發現左右都要排序，又要比大小，不就跟 merge sort 一樣嗎？
對，就是這樣，一邊 merge sort 一邊算答案就好。

（這種方法叫 CDQ 分治）

## 最大連續和

給定 $a_1,\ a_2,\ \dots,\ a_n$，求最大連續和？

跟剛剛一樣的想法
長度為 $n$ 的陣列中一共有 $n^2$ 種區間 $[i,\ j]$
一樣分成三種：

1. $(i,\ j)$ 都在左邊
2. $(i,\ j)$ 都在右邊
3. $(i,\ j)$ 一個在左邊，一個在右邊

同樣的，只要這三種取最大值就能得到答案，第一種和第二種只要往下遞迴就能解決，所以來看怎麼算第三種

只要把左邊 $l_1,\ l_2,\ \dots,\ l_n$ 的後綴最大和 跟 右邊 $r_1,\ r_2,\ \dots,\ r_n$ 的前綴最大和 相加
就能得到答案。
怎麼算 $l_1,\ l_2,\ \dots,\ l_n$ 的後綴最大和 跟 右邊 $r_1,\ r_2,\ \dots,\ r_n$ 的前綴最大和？
就暴力的硬算就好，暴力算的複雜度 $\mathcal O(n)$
總共會要算 $\log n$ 次，所以總複雜度是 $\mathcal O(n \log n)$