## 概念複習
1. 結構 Struct
2. 指標 Pointer
3. 動態記憶體配置
## 結構 Struct
通常是拿來自定義資料 type，比如醫院要記錄病人的姓名、年紀、性別、健保卡號、看病日期等等
這時候用 struct 將這些資料的 type 整合到一起就會變得很方便，以下是範例

struct point {
    int x, y ;
}

point p[100] ;
p[0].x = p[0].y = 1 ;

如果想要直接在 struct 內部初始化元素，有兩種做法

struct point {
    point* next = NULL ;
    int x = 0, y = 0 ;
}

struct point {
    point* next ;
    int x, y ;
    point() : next(NULL), x(0), y(0) ;
    // point(int xn, int yn, point* nxtp = NULL) 
    //     : next(nxtp), x(xn), y(yn)
}
// point(a, b) ; -> x = a, y = b, next = NULL

## 指標 Pointer
指標也是一種變數，但是並非用於儲存常見 type 的值，而是"儲存那些值的記憶體空間"的地址
以下是指標的基礎用法

int a = 10 ;
int* p = &a ;
cout << "the value of a is " << *p << '\n' ;

int arr[3] = {1, 2, 3} ;
int* pa = arr ;

for (int i=0;i<3;i++)
    cout << "arr[" << i << "] is " << *(pa+i) ;

當然最常用的情況還是在 function 傳遞參數，用指標才能修改不同 function 的變數

void swap_ab(int* a, int* b) {
    int tmp = *a ;
    *a = *b ;
    *b = tmp ;
    return ;
}

不過以上這個情況在 C++ 中可以利用傳參的方式

void swap_ab(int &a, int &b) {
    int tmp = a ;
    a = b ;
    b = tmp ;
    return ;
}

最後雙重指標有可能用在二維指標，但是在 C++ 的情況下不常用就不贅述了
## 動態記憶體配置
動態記憶體配置適合用在需要新增、修改、刪除等操作的變數

int *p1 = new int ;
int *p2 = new int(7) ;

*p1 = 10 ;
cout << *p1 << ' ' << *p2 << '\n' ;

delete p1 ;
delete p2 ;

當然不是只有變數可以用，也可以用在陣列這種資料結構上

int *pa1 = new int[3] ; // size 3
int *pa2 = new int[3]{1, 2, 3} ;
...
delete[] pa1 ;
delete[] pa2 ;

甚至在二維陣列上也可以

int main() {
    int **pta = new int*[4] ;
    for (int i=0;i<3;i++)
        pta[i] = new int[4]{0} ; // array [4][4]

    pta[0][1] = 1 ;
    pta[1][1] = 2 ;
    pta[2][1] = 3 ;
    
    ...
    
    for (int i=0;i<4;i++)
        delete[] pta[i] ;
    delete[] pta ;

    return 0 ;
}

但最常用的還是搭配 struct 去做使用，通常是在 Linked List 這種動態資料結構上面

struct point {
    int x, y ;
    point* next ;
};

point *p1 = new point ;
point *p2 = new point ;

p1->x = 1, p1->y = 2 ;
p1->next = p2 ;

p2->x = 3, p2->y = 4 ;
p2->next = NULL ;

cout << p1->x << ' ' << p1->y << '\n' ;
cout << (*p2).x << ' ' << p1->next->y << '\n' ;

delete p1 ;
delete p2 ;

當然動態記憶體使用完記得都要用 `delete` 刪除，不然可能會出現問題

---
接下來都是之前沒提過的概念，主要的目的是作為幫助理解之後篇章與一些前置知識
## 雙指針
在同一個資料結構上用兩個指針(指標)進行操作，這兩個指針可以在同個位置，也可以在不同位置
兩個指針可以同向(同時往右或往左)，也可以不同向(兩個靠近或遠離)，也可以獨立運動
獨立運動就是某一指針移動不會影響另一指針，所以當一個指針移動，另外一個可以不動或移動
常見的雙指針可能會拿來比較兩指針對應的值，維護一個特定區間，以下給一些常見的應用
1. Sliding window: 維持一個動態區間，使區間可以滿足特定條件，兩個指針同向
2. 兩指針靠近+判斷: 迴文、排序後陣列找兩值相加為特定值
3. 快慢指針: 一個指針移動較快，另一個指針移動較慢
4. 折半指針: 將資料結構或問題拆成兩半，一個指針負責一半，各自計算再合併結果
5. Shrinking interval: 維護一個區間`[l, r]`，然後根據條件縮小範圍直到找到答案
6. 多序列雙指針: 兩個以上的已排序陣列用指針遍歷，通常用在合併排序上面

基本上目前只要知道前兩個，其餘的目前也不是很重要，但是是有使用到雙指針的一種實作

## 單調性
資料和函數值在某個範圍內保持遞增或遞減的性質就稱為"單調性"，用數學的語言來說
1. 單調遞增: 對於任意 $i<j$，必定 $f(i) \le f(j)$、或 `A[i] <= A[j]`
2. 單調遞減: 對於任意 $i<j$，必定 $f(i) \ge f(j)$、或 `A[i] >= A[j]`

所謂的單調性，不一定是題目給定的結構有單調性，也可以主動去做一個具有單調性的結構
不過這單元不會講太多程式碼，因為只是介紹一下單調性而已

單調性最主要的功能就是讓資料變得可預期，有了可預期的資料後就能更容易做優化
比如把問題拆成大於 $X$、不大於 $X$ 兩個部分，再去做處理，最典型的例子就是二分搜
每次處理都會縮減一半的範圍，就是基於單調性在這個問題的應用

以下列出四個比較常見的應用
1. 二分搜
2. 雙指針、Sliding window
3. 單調資料結構
4. 單調 DP

拿點一來說明，假設要找的數字為 $A$，二分搜過程中找到的數字為 $X_1, X_2, ...$
那當我們確定 $A < X_1$，我們就可以確定"如果 $A$ 在資料結構中，位置一定在 $X_1$ 前方"
所以就可以縮減範圍，另一個情況 $A > X_1$ 也是同理，一樣可以縮減範圍
## 快速冪
快速計算 $x^a$ 的方法，這裡的 $x, a$ 都是整數，題目通常會要求結果做 (mod P)
如果用暴力的解法，一個個慢慢乘那效率就會很低，這時候就可以用到指數的特性
* $(a^b) \times (a^b) = a^{2b}、(a^b)\times(a) = a^{b+1}$

有這個特性我們就能高效的處理這個問題，舉個例子，假設我們想求 $2^{25}$，進行拆分的步驟如下:
1. $2^{25} = 2^{24} \times 2$
2. $2^{24} = 2^{12} \times 2^{12}$
3. $2^{12} = 2^{6} \times 2^{6}$
4. $2^{6} = 2^{3} \times 2^{3}$
5. $2^{3} = 2^{2} \times 2$
6. $2^{2} = 2^1 \times 2^1$

其實就是遇到偶數拆成兩個相乘，遇到奇數就拆成一個和 $a$ 相乘

// P = 1000000009
int rec(int a, int b) {
    if (b == 1) return a ;
    if (b & 1) return (rec(a, b-1) * a) % P ;
    // else: even
    int tmp = rec(a, b/2) % P ;
    return (tmp * tmp) % P ;
}

還有一個跟快速冪相關的應用-快速計算費氏數列
$\left[
\begin{array}{ccc}
f(n) \\
f(n-1) \\
\end{array}
\right] =
\left[
\begin{array}{ccc}
1 & 1 \\
1 & 0 \\
\end{array}
\right] \times
\left[
\begin{array}{ccc}
f(n-1) \\
f(n-2) \\
\end{array}
\right]，
\left[
\begin{array}{ccc}
f(1) \\
f(0) \\
\end{array}
\right] =
\left[
\begin{array}{ccc}
1 \\
0 \\
\end{array}
\right]$
由上方公式可以推導出以下公式
$\left[
\begin{array}{ccc}
f(n) \\
f(n-1) \\
\end{array}
\right] =
\left[
\begin{array}{ccc}
1 & 1 \\
1 & 0 \\
\end{array}
\right]^{n-1} \times
\left[
\begin{array}{ccc}
1 \\
0 \\
\end{array}
\right]$
對矩陣做快速冪後就可以很快算出費氏數列 `f(n) = (A^{n-1})[0][0]`
## 預處理
在做主要計算之前，先對資料作處理，讓後續的計算更方便或是更有效
舉個例子，搜尋前先將資料排序好，就能用二分搜，這裡的排序就是預處理，以下是常見的預處理
1. 前綴和、前綴 XOR、差分
2. 建表(比如質數表、最短路徑表、LCA 表、DP 狀態表)
3. Rolling Hash
4. Sparse Table

基本上預處理就是在用一定的時間、空間去換取後方主要計算的效率
所以在預處理的時間超過後方主要計算的情況下，不如放棄預處理直接開始主要計算