---
tags: 嘉中資訊科培訓講義
---
# 嘉中資訊科培訓講義(elementary level)
作者：[vincent97198](https://vincent97198.blogspot.com/)、[エミリア](https://oemiliatano.github.io/)
---
> [TOC]
>
> [這些都學過了，讓我離開新手村!](https://hackmd.io/x1u_TyWNSuGL9Wg_mTKlSw)
---
## 零、概論
我相信會用到這個題單的人，已經解完基礎的題單了><
所以接下來的內容，會省略掉我認為你們應該會的東西，然後多做一些補充。
這是一份花了幾天、犧牲考試成績等價交換出來的講義，好好珍惜。
> 練習題有時候會需要已經教過但非該章的知識，請自行思考。
---
### Online Judge
[UVa](https://onlinejudge.org/), [Atcoder](https://atcoder.jp/), [codeforces](https://codeforces.com/), [TIOJ](https://tioj.ck.tp.edu.tw/), [POJ](http://poj.org/), [Luogu](https://www.luogu.com.cn/)
---
### 主要競賽
* 請多打線上比賽，友cf、友at、最重要的，~~友CYSH Online judge~~。
如果你想進1!或更高，請拿出毅力打cf，at就不用了；它都8點開始。
> codeforce 的出題方向和TOI不太一樣，不要練到走火入魔了
> 等你大學打ICPC的時候就可以練cf練到走火入魔了(?
---
### 複雜度
* 時間複雜度
* 常見的複雜度
__dfs, bfs__ is $O(E + V)$
__many data structrue__, __build__ is $O(n)$, __require__ is $O(logn)$, __modify__ is $O(logn)$
__sort__ is $O(nlogn)$
__lower/upper_bound__ is $O(logn)$
__floyd warshall__ is $O(V^3)$
__Dijkstra__ is $O((V+E)logV)$
__set.count()__ is $O(log n)$
__multiset.count()__ => Logarithmic in size and linear in the number of matches.
* 空間複雜度
同時間複雜度去分析
_i.e._ 常數空間, 線性空間...
* coding複雜度
程式碼很長、容易出bug的就是高coding複雜度
一般來說，數學題的coding複雜度最低，而資料結構題的coding複雜度最高。
* 均攤分析
假設有一連串的操作，大部分代價小，而少部分代價大，那他們的代價可以均攤到每筆操作上，如果這樣整體代價仍然合理，那就可以敲code了。
實際上，這裡面有很深的學問，在此不展開講解。
i.e 並查集, 單調隊列
* $10^8$法則
把數據範圍代進複雜度裡，除以$10^8$後的數字，就代表會跑幾秒。
這是經驗法則。
且會隨著時間、judge有所不同。但是不失為一個判斷能否AC的好方法。
---
### 前國手們的建議
心法分享： （不知道會不會有智慧財產權的問題就先撤掉了）
解題技巧：
## 一、基礎演算法與技巧整理
### Greedy
多數情況下，Greedy策略是假解，請務必小心使用。
~~（不過在IOI賽制下還是可以拿來喇分）~~
* __如何看出Greedy__
通常整題都考Greedy的題目，n都不小。
其他就是要多觀察題目的性質
* __如何證明Greedy是對的？__
怕自己Greedy假解的好方法就是：
把Greedy的想法寫成DP式的樣子，然後檢查DP轉移有沒有漏考慮了什麼。
或是直接做，靠通靈。
---
### 二分搜
* 上界/下界值其實可以開很大。反正頂多搜128次而已。
請小心設定退出條件。
* 二分搜用途及廣，他可以搜很多東西，最稀疏平常的就是搜答案
有許多問題都喜歡叫你求「滿足條件的最小值」。
這類問題若能滿足以下條件，那或許可以考慮對答案二分搜。
* 任何大於答案（滿足條件的最小值）的數，都能滿足條件
* 判斷一數能否滿足條件的時間複雜度是好的，記得複雜度會帶個$O(logn)$
練習題: [poj 3685](http://poj.org/problem?id=3685), [zj c904](https://zerojudge.tw/ShowProblem?problemid=c904), [zj c575](https://zerojudge.tw/ShowProblem?problemid=c575)
---
### 三分搜
* __用法__
三分搜尋法和我們熟悉的二分搜尋法在實做層面上，算是差不多的東西，唯一不同的地方在於
* 二分搜尋法用於 __尋找單調函數的某個值__
* 三分搜尋法則是用於 __尋找n次函數的某個值__
> 須確定搜索的範圍內函數的形狀是U或∩才行
* __原理__
假定要拿來解釋的這個是要找二次函數的極小值，且極值的位置在左右界內僅靠一個參考點無法得知，該點的左右何者較接近極小值，但若有2個參考點（也就是三等份）就能得知較小的點必定比另一點更靠近極小值（二次函數性質），就能因此鬆弛解的範圍
__實作__ (U型函數)
```cpp=
while(fabs(l - r) > s)
{
m1 = (l + l + r) / 3
m2 = (l + r + r) / 3;
if (f(m1) > f(m2))
l = m1;
else
r = m2;
}
```
* __複雜度__ $O(log n)$
練習題: [AtCoder Beginner Contest 130 pF](https://atcoder.jp/contests/abc130/tasks/abc130_f)
---
### 打表
有的時候題目的形質非常神秘，不易觀察（尤其是數學題(~~玄學題~~）)
我建議可以本地打表，觀察性質，可能會有助於思考(吧
練習題: [zj e320](https://zerojudge.tw/ShowProblem?problemid=e320), [cf 1342C](https://codeforces.com/problemset/problem/1342/C)
---
### 本地爆搜
本地算完答案或一些關鍵數字，藉此壓縮複雜度。
（面對難題或許有奇效 ~~通常沒有~~）
練習題: [zj e299](https://zerojudge.tw/ShowProblem?problemid=e299)
---
### 時間剪枝
快要TLE時，不管答案是否最優，直接輸出答案。
或是搜什麼東西，結果時間快到了還搜不到，直接輸出不存在。
(喇分還是挺有效的。)
---
## 二、資料結構
> 工欲善其事，必先利其器
### 線段樹
大概是資料結構的新手技能吧。 ~沒有人不會的。~
生來就是解決 __區間__ 問題。
> 給定一長度為n的數列，求區間$l, r$的最大/小值、和。
* __原理__
將一段數列，分治處理，利用分治的技巧，整個線段最多被切割$logn$次。藉此可以很快的維護線段的查詢、修改。
* __lazy tag__
> 現在增加一操作: 在區間$l,r$加上$v$
>
當原本的線段樹遇到區間加/減值時，單點修改會TLE，lazy tag即是利用 __不使用就不更新__ 的想法，在某個區間上打上tag，代表這裡的子節點應修改，然後不管他直到查詢需要用到才把tag推到子節點。
> 類似硬碟的刪除標記(?
>
* __差分__
> 給定原陣列$A$，現有兩操作
> 1. 在區間$l, r$內加上一首項為$k$、公差為$d$的等差數列
> 2. 詢問索引$p$的數。
>
如果我們現在在一般數列$b_i$存入$A_i$與$A_{i-1}$的差，而首項為$A_1$，我們可以知道這樣的陣列有一些性質
1. 前綴和$S_i=a_i$
2. 區間$l,r$加值相當於$b_l+v, b_{r+1}-v$
於是我們如果維護這樣一個數列，對於操作1，我們可以很簡單的先$b_l+k,b_{r+1}-(k+(r-l)\times d)$，而後整個區間$l+1,r$加上$d$。
明顯的，我們可以用線段樹維護上述數列，查詢前綴和即可。
練習題: [zj d801](https://zerojudge.tw/ShowProblem?problemid=d801), [luogu P1438](https://www.luogu.com.cn/problem/P1438)
---
### Sparse Table
又稱稀疏表。很少用到。
只能用在RMQ(Range Minimum/Maximum Query)，不能算區間和。
* __原理__
與許多資料結構的想法一樣，先處理小部分，在合併成整體。
定義`Table[i][j]`為，在索引值i處，長度為$2^j$的數列最大/小或和，甚至乘。
__build__: $O(nlogn)$
__query__: $O(1)$
__modify__: __it can't be modified__
* __使用時機__
不需要修改，大量尋找區間極值時。
但是很少會用到，但是一旦用到絕對比刻一顆線段樹還快很多。
* __實做__
__build__:
先預處理長度為1的段。
```cpp=
for (int32_t i = 0; i < n; ++i)
for (int32_t j = 1; i - 1 + (1 << j) < n; ++j)
Table[i][j] = maintain(Table[i][j - 1], Table[i + (1 << (j - 1))][j - 1]);
```
__query__:
```cpp=
int32_t k = log2(r - l + 1); // int len = __lg(r - l + 1);
auto ans = maintain(Table[l][k], Table[r - (1 << k) + 1][k]);
```
> 跟倍增法好像哦
---
### BIT ~這是エミリア最喜歡的資料結構之一。~
~~學好BIT說不定就可以看見她的笑容~~
不是你惠惠。
* __原理__
首先要先知道`lowbit(x)`在幹嘛，此函數會回傳x在二進制下最低的1是多少
_i.e._ `lowbit(3 = 0b11) = 1`, `lowbit(6 = 0b110) = 2`
而實作上可以用 `x&(-x)` 來取得。
定義`bit[x]`維護了$(x-lowbit(x), x]$的區間和。
(如果你還是不懂，可以畫圖看看)
那 __單點修改__ 就是
```cpp=
for (int32_t i = pos; i <= maxn; i += lowbit(i))
bit[i] += value;
```
__前綴查詢__:
```cpp=
for (int32_t i = pos; i; i -= lowbit(i))
res += bit[i];
```
如果將元素的值當作下標；且在下標處+1的話，可以擴展使用下面的功能
__第k小查詢__:
錯誤範例複雜度：$O(log^2n)$
```cpp=
//錯誤範例
int32_t l = 0, r = maxn;
while(r > l)
{
int32_t mid = (r + l) / 2;
if(k > sum(mid))
l = mid + 1;
else
r = mid;
}
res = mid;
```
正確解法複雜度：$O(logn)$
```cpp=
//正確範例
res = 0;
for (int32_t i = (1<< floor(log2(maxn))); i; i >>= 1)
if (res + i <= maxn && bit[res + i] < k)
k -= bit[res += i];
++res;
```
* 複雜度
__modify__: $O(logn)$
__query__: $O(logn)$
* 使用頻率
不算很低，也不算很高，但是很方便，算是輕便型segment tree
* 優點
常數很小、coding複雜度小
> 練習題: [tioj 1282](https://tioj.ck.tp.edu.tw/problems/1282), [zj b577](https://zerojudge.tw/ShowProblem?problemid=b577), [zj d847](https://zerojudge.tw/ShowProblem?problemid=d847)
---
### treap ~同樣是エミリア最喜歡的資料結構之一~
__!這裡只討論split-merge treap__
屬於二元平衡樹的一種，因為 __易編寫__ __速度快__ __靈活性高__ 的特性而在競程占有一席之地。
他可以解決 segment tree 的問題，也可以解決splay tree的問題，同樣也可以解決大部分二元平衡樹的問題，學一個treap抵過學一堆樹。
* __基本原理__
Treap = tree + heap。
亦即同時擁有BST與heap性質的資料結構。
> heap: 父節點的```pri```值大於子結點
> BST: 左子樹```key```值均小於等於父節點，右子樹則大於。
>
> 一般二元平衡樹為了避免退化，會利用 __旋轉__ 操作去維持深度。
> 而treap因為擁有BST與heap的性質，所以既能擁有BST的查找功能，又能像heap一樣維持深度，
- __treap最重要的兩個操作:__
- merge(a, b):
合併兩顆treap，注意此函式必須滿足 __a的所有key值小於b的所有key__
- split(t, k):
將treap t分成兩顆treap， __一顆裡的key均小於等於k，另一顆的均大於__。
兩種操作都因為BST的特性所以實作難度降低許多。
* __基本架構__
* __node:__
```cpp=
struct Treap
{
Treap *l, *r;
int32_t key, pri;
Treap(int32_t _key)
{
l = r = nullptr;
key = _key;
pri = rand();
}
}
```
* __merge:__
```cpp=
Treap* merge(Treap* a, Treap* b)
{
if (a == nullptr || b == nullptr) return a ? a : b;
if (a->pri > b->pri)
{
a->r = merge(a->r, b);
return a;
}
else
{
b->l = merge(a, b->l);
return b;
}
}
```
* __split:__
```cpp=
void split(Treap* t, int32_t k, Treap* &a, Treap* &b)
{
if (t == nullptr)
{
a = b = nullptr;
return;
}
if (t->key <= k)
{
a = t;
split(t->r, k, a->r, b);
}
else
{
b = t;
split(t->l, k, a, b->l);
}
}
```
只要有上面兩種操作，基本就寫完了。
* __insert:__
```cpp=
void insert(Treap *t, int32_t k)
{
Treap *lt, *rt;
split(t, k, lt, rt);
merge(merge(lt, new Treap(k)), tr);
}
```
* __remove:__
```cpp=
void remove(Treap *t, int32_t k)
{
Treap *lt, *rt;
split(t, k - 1, lt, t);
split(t, k, t, rt);
t = merge(lt, rt);
}
```
__treap，就是這麼簡單。__
在平衡樹的問題中，常常遇見尋找第k小元素的要求，就跟BST一樣，treap一樣是用節點size去判斷，所以我們現在需要維護treap上節點的size，這樣可以跟BST一樣找kth了。
```cpp=
int32_t Size(Treap *t)
{
return t == nullptr ? 0 : t->sz;
}
void pull(Treap *t)
{
t->sz = 1 + Size(t->l) + Size(t->r);
}
```
* __真正實作__
__node:__
```cpp=
struct Treap
{
static Treap mem[MAXN], *ptr;
Treap *l, *r;
int32_t pri, key, siz;
Treap() = default;
Treap(int32_t _key)
{
l = r = nullptr;
pri = rand(); //可以用其他隨機方法，保證更好的隨機性
key = _key;
siz = 1;
}
}Treap::mem[MAXN], *Treap::ptr = Treap::mem;
```
__split:__
```cpp=
//與上面唯一有差別的只有當某顆treap的結構改變時，需要呼叫pull()去更新資訊
//例如 呼叫完split()後
```
__merge:__
```cpp=
//與上面唯一有差別的只有當某顆treap的結構改變時，需要呼叫pull()去更新資訊
//例如 呼叫完merge()後
```
__kth:__ (第k小)
```cpp=
int32_t kth(Treap *t, int32_t k)
{
int32_t lsz = sz(t->l) + 1;
if (lsz < k) return kth(t->r, k - lsz);
else if(lsz == k) return t->key;
else return kth(t->l, k);
}
```
__以上是treap當平衡樹的版本__
---
* __treap區間維護__
上面提過，treap不只可以解決平衡樹問題，也可以解決序列操作問題。
我們只需要在node裡多加一個```val```當作序列上的值、```key```當作序列上的索引值、```mx/mn/sum```當作要維護的值即可。
__treap，就是這麼簡單。__
但是當我們遇到區間加值怎麼辦?
線段樹巧妙的用 __lazy tag__ 解決了，同樣的treap也可以!
只要用好好維護我們的tag即可。
```cpp=
void push(Treap *t)
{
if (t == nullptr) return;
t->val += t->lazy;
t->mx += t->lazy;
if (t->l != nullptr)
t->l->lazy += t->lazy;
if (t->r != nullptr)
t->r->lazy += t->lazy;
t->lazy = 0;
}
void pull(Treap *t)
{
t->sz = 1 + Size(t->l) + Size(t->r);
}
```
__node:__ (改)
```cpp=
struct Treap
{
static Treap mem[MAXN], *ptr;
Treap *l, *r;
int32_t pri, key, siz, lazy;
int32_t val; //新增這兩個
int32_t mx;
Treap() = default;
Treap(int32_t _key, int32_t _val)
{
l = r = nullptr;
pri = rand();
key = _key;
siz = 1;
val = mx = _val;
}
}Treap::mem[MAXN], *Treap::ptr = Treap::mem;
```
__build:__
```cpp=
Treap *t = nullptr;
for (int32_t i = 1; i <= n; ++i)
t = merge(t, new (Treap::ptr++) node(i, a[i]));
```
上面用到了placement new的技巧，通過先開記憶池再去new一個node，可以降低系統分配記憶體的開銷。
__區間加值:__
```cpp=
void add_range(Treap *t, int32_t l, int32_t r, int32_t val)
{
Treap *lt, *rt;
split(t, l - 1, lt, t);
split(t, r, t, rt);
t->lazy += val;
merge(merge(lt, t), rt);
}
```
---
* __翻轉吧! treap__
有沒有觀察到我們剛剛 __build__ 時，```key```直接放1, 2, 3...，仔細想想這樣```key```的意義不就是 __在treap中有幾個比他小__。
那只要維護好```size```就可以不用管```key```了。
所以```split(t, k)```的意義也就變成了:__在t中切開前$k$個節點與後$n - k$個節點__。
* 只用```size```的好處
不必再被```key```綁手綁腳的，當我們遇到什麼區間翻轉、區間剪下貼上，就真的直接剪下去、或轉下去(正常還是會打標)。
__treap，就是這麼簡單__
__node:__ (改)
```cpp=
struct Treap
{
static Treap mem[MAXN], *ptr;
Treap *l, *r;
int32_t pri, siz, lazy;
int32_t val;
int32_t mx;
bool rev; //翻轉標記
Treap() = default;
Treap(int32_t _val)
{
l = r = nullptr;
pri = rand();
siz = 1;
val = mx = _val;
rev = false;
}
}Treap::mem[MAXN], *Treap::ptr = Treap::mem;
```
__split:__ (改)
```cpp=
void split(Treap *t, int32_t k, Treap *&a, Treap *&b)
{
if (!t) { a = b = nullptr; return; }
push(t);
//此節點的左子樹數量大於等於k
if (Size(t->l) >= k)
{
b = t;
push(b);
//將b指向整個樹，向左子樹處理。
split(t->l, k, a, b->l);
pull(b);
}
else
{
a = t;
push(a);
split(t->r, k - Size(t->l) - 1, a->r, b);
pull(a);
}
}
```
這部分的```split()```比較難理解，可以畫圖看看或直接貼程式，輸出中間過程。
!翻轉其實就是左右子樹交換
練習題: [luogu P3391](https://www.luogu.com.cn/problem/P3391)(模板), [cf 702F](http://codeforces.com/problemset/problem/702/F)
---
## 三、圖論
>
資訊的圖是由 __點(vertex)__ __邊(edge)__ 構成的。
圖有下面幾種:
1. 有向圖 : 邊有方向性
2. 無向圖 : 邊無方向性
3. 簡單圖 : 無重邊、無自環
4. 完全圖 : 所有點彼此互連
5. 二分圖 : 把圖分成兩部分，同一個集合裡的點 __彼此不相連__，且圖上不存在奇環
---
### 專業術語
1. $DAG$ : 有向無環圖
2. $|V|$ : 點的個數
3. $|E|$ : 邊的個數
---
### 樹
圖論中的樹，指的是有$n$個點、$n-1$條邊，每個點都相連通的圖。
#### 樹直徑
> 要求兩端點$i$, $j$使得$dis(i, j)$為樹中最大，求$i$, $j$, $dis(i, j)$，
有DP、兩種dfs作法，這裡只介紹dfs。
1. __兩次dfs作法__
隨機一頂點找最遠點v，再由v去找離v最遠的點u，則(u,v)為樹直徑兩端，直覺無比皆大歡喜。
```cpp=
// 沒有code啦，難道dfs也不會？
```
2. __一次dfs作法__
樹dp
```cpp=
int32_t ans = 0;
int32_t dfs(int32_t now, int32_t pa)
{
int32_t MAX = 0, MAX2 = 0; //目前節點第一,二長路徑
int32_t nexDep;
for (auto next : G[now])
{
if (next == pa) continue;
nexDep = dfs(next, now);
if (nexDep > MAX)
MAX2 = MAX, MAX = nexDep;
else if (nexDep > MAX2)
MAX2 = nexDep;
}
ans = max(MAX + MAX2, ans);
return MAX + 1; //只需要回傳這個節點下最大的路徑長就好
}
```
---
#### 最近共同祖先(LCA)
> 給定$root, a, b$，有$Q$個詢問求$a, b$的共同祖先$c$，且$c$距離兩者皆最小。
- __naive解__
dfs一遍，確定每個點的父親以及深度，然後從$a, b$往上爬到同樣的節點即可。
- 複雜度: $O(Qn)$
- __倍增法__
從剛剛的naive解我們會發現我們每次都只是往上走 __1__ 而已，何不走大步一點呢?
如果每次我們都走2的冪次步的話，可以走到任意祖先。 (二進制的性質)
那我們就預處理每個點往上走$2^j$步會到誰就好了。
當詢問時，就開始跳，直到相同的點。
```cpp=
void dfs(int32_t now, int32_t fa = -1)
{
for (int32_t i = 1; i < 32; ++i)
{
//maintain
MX[now][i] = MX[Father[now][i - 1]][i - 1];
Father[now][i] = Father[Father[now][i - 1]][i - 1];
}
for (auto node : G[now])
{
int32_t to = node.first;
int32_t wi = node.second;
if (to == fa) continue;
//maintain
MX[to][0] = Val[now][to];
Father[to][0] = now;
depth[to] = depth[now] + 1;
dfs(to, now);
}
}
```
```cpp=
int32_t lca(int32_t u, int32_t v)
{
if (_depth[u] > _depth[v]) swap(u, v);
int res = INT_MIN;
int tmp = _depth[v] - _depth[u];
for (int32_t i = 0; tmp; ++i, tmp >>= 1)
if (tmp & 1)
{
//maintain
res = max(res, MX[v][i]);
v = _Father[v][i];
}
if (u == v) return u;
for (int32_t j = 31; j >= 0 && u != v; --j)
if (_Father[u][j] != _Father[v][j])
{
//maintain
res = max({res, MX[u][j], MX[v][j]});
u = _Father[u][j];
v = _Father[v][j];
}
//return _Father[u][0];
return max(res, MX[u][0]);
}
```
__複雜度__: build: $O(N)$, query: $O(logN)$
---
#### dfs序
> 給定一棵樹及根，上面有$n$個節點，每個節點都有一顏色$c_i$，總共有$m$個操作，有兩種操作:
> 1. 將$v$的子樹染色成$k$
> 2. 詢問$v$的子樹裡包含幾種顏色
>
> $n, m\leq 4\times 10^5$ , $c_i \leq 60$
首先考慮這棵樹是一條直鍊的情況。
用位元去表示顏色，拿個資料結構實現可以查找區間OR的功能就好了。
那當這棵樹不只一條鍊的話怎麼辦?
如果點集合$S$是$v$的子樹，那點集$S$必然比$v$還要晚被dfs到，也就是說假設我們現在有一棵樹，dfs下去，那每個點都有他進去的順序。
_i.e_ root = 1, root's son1 = 2, root's son2 = 3 ...etc.
而你會發現如果將這序號排好，$v$的子樹，就是其中的一段區間。
而$l$就是$v$的序號，$r$則是$v$子樹中最大的序號(或是$l + size - 1$)。
至此，我們只需要一次dfs找序號，用一支援區間OR的資料結構即可解決問題。
一些樹上問題可以透過dfs序解決，當然也需要點巧思才能將問題轉化。
例如
> 給定一棵樹一個根，總共$n$個點，有$q$個查詢，問$i$是不是$j$的 __祖先__
>
如果只單看進入時間根本看不出來，一個不夠? 那就看兩個。
連同 __離開時間__ 一起看。
細節自己想想，這邊不多贅述。
---
[本章](###樹)練習題: [USACO 2019.12 Platinum Bessie's Snow Cow](https://loj.ac/problem/3227), [cf 620E](https://codeforces.com/problemset/problem/620/E)
---
### 一般圖的連通性
#### dfs邊分類
- 樹邊: 真正在dfs樹上的邊，從父親連往小孩
- 回邊: 從子孫連回祖先的邊
- 交錯邊: 連向非直系血親的邊
#### 無向圖的連通性
> 定義一連通圖$G$為 __點-$k$-連通__，滿足刪去$k-1$個 __節點__ 能使$G$變得不連通。
>
> 定義一連通圖$G$為 __邊-$k$-連通__，滿足刪去$k-1$個 __邊__ 能使$G$變得不連通。
>
競賽中最常見的$k=2$，分別被稱為 __點雙連通__ 及 __邊雙連通__
- __邊雙連通__
- 性質: 對於點雙圖中的點$u, v$，至少存在兩條路徑從$u$到$v$，且不共邊。
- Robbin定理: 對於一無向圖$G$，$G$是邊雙連通若且唯若存在一種將G的邊定向的方式使任兩節點可以互相到達。
定義 __橋__(bridge): 若$e$是橋，則移除後會使圖$G$不連通。
所以只要能夠找到橋就可以判斷圖$G$是否為邊雙連通。
- __Tarjan's Algorithm__
定義 __low(v)__:對於無向圖的節點$v$，$low(v)$被定義為在不透過父邊，能夠到達的最低祖先的深度
!上圖的節點4可以走到2，所以$low(4)=1$；節點7可以走到1，所以$low(7)=0$，而3可以通過4走到2，所以$low(3)=low(4)=1$，其餘相同。
可以發現當$low(v)$與$dep(v)$一樣時，$e=\{v, fa(v)\}$為橋。
- __實作__:
```cpp=
void dfs(int32_t now, int32_t fa)
{
vis[now] = true;
low[now] = dep[now] = dep[fa] + 1;
for (auto nex : G[now])
{
if (nex == fa)
continue;
if (vis[nex])
low[now] = min(low[now], dep[nex]);
else
{
++childcnt;
dfs(nex, now);
low[now] = min(low[now], low[nex]);
}
}
if (low[now] == dep[now])
{
// edge{now, pa} is bridge unless now is root
}
}
```
複雜度:$O(E+V)$
- __邊雙連通分量__
雙連通分量指的是圖$G$裡的 __雙連通子圖__。
一般是指極大的連通子圖，也就是說無法在該子圖中添加新節點，使得新加入的子圖仍滿足雙連通。
如何找到邊雙連通分量?
- __naive解__
把所有橋都移除掉，剩餘的就是邊雙連通分量。
複雜度: $O(2(V+E))$
- __tarjan解__
在遞迴過程中維護一個stack，在每次進入一個節點的時候把它推入stack中，當我們確定節點$v$的父邊為橋時，在stack裡由上而下直到節點$v$就都是邊雙分量。
```cpp=
void dfs(int32_t now, int32_t fa)
{
vis[now] = true;
low[now] = dep[now] = dep[fa] + 1;
st.push(now);
for (auto nex : G[now])
{
if (nex == fa)
continue;
if (vis[nex])
low[now] = min(low[now], dep[nex]);
else
{
dfs(nex, now);
low[now] = min(low[now], low[nex]);
}
}
if (low[now] == dep[now])
{
// edge{now, pa} is bridge unless now is root
while(!st.empty())
{
int32_t x = st.top(); st.pop();
bcc[x] = Nbcc;
if (x == now) break;
}
++Nbcc;
}
}
```
複雜度: $O(V+E)$
當我們找到雙連通分量後，就可以根據編號而縮點，縮完點後的圖 __不會存在環__，這是個好的性質，這樣的圖常常存在複雜度好的算法。
---
- __點雙連通__
- 性質: 對於兩個圖中節點$u, v$，都存在兩條從$u$到$v$的路徑，且無共用點。
定義 __割點__ 或 __關節點__: 若$v$是割點，則移除後圖$G$不連通
- __tarjan's algorithm__
沿用上面的low()定義，有一個節點$v$以及子節點$u$，若有一個$u$的$depth(v)\leq low(u)$，則節點$v$必為割點。
!但是root需要特判
```cpp=
void dfs(int32_t now, int32_t fa)
{
int childcnt = 0;
vis[now] = true;
low[now] = dep[now] = dep[fa] + 1;
for (auto nex : G[now])
{
if (nex == fa)
continue;
if (vis[nex])
low[now] = min(low[now], dep[nex]);
else
{
++childcnt;
dfs(nex, now);
low[now] = min(low[now], low[nex]);
if (low[nex] >= dep[now])
cut[now] = true;
}
}
if (now == root && childcnt <= 1)
cut[now] = false;
}
```
- __點雙連通分量__
與上面的邊雙連通分量一樣，我們一般討論極大點雙連通子圖。
但是會有一個問題:
可以發現一個點可能會被分在不同的分量中，而這情況只發生在割點，因此若是我們使用上面的方法:存點，可能會把割點pop掉，但是實際上還有其他分量包含著，因此找點雙連通分量時，我們必須存邊
- __tarjan解__
```cpp=
void dfs(int32_t now, int32_t fa)
{
int childcnt = 0;
vis[now] = true;
low[now] = dep[now] = dep[fa] + 1;
for (auto nex : G[now])
{
if (nex.node == fa)
continue;
if (!inStack[nex.edgeNum])
{
inStack[nex.node] = true;
st.push(nex.edgeNum);
}
if (!vis[nex.node])
low[now] = min(low[now], dep[nex.node])
else
{
++childcnt;
dfs(nex.node, now);
low[now] = min(low[now], low[nex.node]);
if (low[nex.node] >= dep[now])
{
cnt[now] = true;
while(!st.empty())
{
int e = st.top(); st.pop();
bcc[e] = Nbcc;
if (e == nex.edgeNum) break;
}
++Nbcc;
}
}
}
if (now == root && childcnt == 1)
cut[now] = false;
}
```
點雙連通分量可以建成一種特殊的樹，__圓方樹__，對於割點$v$如果把它獨立看做一點，而點雙分量也看成獨立一點的話，就會變成
割點為圓點，而方點為連通分量。
---
#### 有向圖的連通性
> 定義一有向圖為 __弱連通__，若圖上所有邊都換為無向邊後圖連通。
> 定義一有向圖為 __強連通__，對於兩個節點$u,v$都存在一條從$u$走到$v$以及一條從$u$到$v$的路徑。
>
- __強連通分量__
同無向圖一樣，我們都只討論極大子圖。
- __Kosaraju algorithm__
```cpp=
void reDfs(int32_t now)
{
vis[now] = true;
for (auto nex : rG[now]) //rG為G的反圖
if (!vis[nex])
reDfs(nex);
order.push_back(now);
}
void dfs(int32_t now, int32_t s)
{
scc[now] = s;
for (auto nex : G[now])
if (scc[nex] == -1)
dfs(nex, s);
}
void Kosaraju()
{
for (int32_t i = 0; i < n; ++i)
{
if (!vis[i])
reDfs(i);
}
int32_t NScc = 0;
for (int32_t i = n - 1; i >= 0; --i)
{
int32_t now = order[i];
if (scc[now] == -1)
dfs(now, NScc++);
}
}
```
---
> [本章](###一般圖的連通性)練習題 :[tioj 1981](https://tioj.ck.tp.edu.tw/contests/71/problems/1981), [cf 1220E](https://codeforces.com/problemset/problem/1220/E)
---
## 四、DP ~這是エミリア最討厭的東西~
### 背包
算是DP入門的新手技，但是有許多變體。
---
#### 完全背包
> 給定n個物品，每種物品都有重量與價值，__且每種物品有無限個__，你最多可以拿M單位重物品，求最大價值
* __code:__
```cpp=
for (int32_t i = 1; i <= n; ++i)
for (int32_t j = w[i]; j <= M; ++j)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
```
其實就只是01背包的 __枚舉順序相反__ 而已
練習題: [luogu P1616](https://www.luogu.org/problemnew/show/P1616)
---
#### 多重背包
> 給定n個物品，每種物品都有重量與價值，__且每種物品有$c_i$個__，你最多可以拿M單位重物品，求最大價值
>
* 用01背包的方式去做
每 __件__ 物品都去跑01背包，則複雜度: $O(M\sum c_i)$
相信這應該不是好的複雜度。
* 二進制優化
在上面的例子中，我們的時間都浪費在重複選取上面了。
例如: 同時選第1種物品的第1, 2個 跟 第1, 3個是相同的。
那麼優化拆分方式就成了關鍵。
這裡要介紹的即是 二進制分組:
> 把同種類的$c_i$個物品不斷包裝成價值$v_i \times 2^j$、重量$w_i \times 2^j$
可以發現因為二進制的關係，雖然那些單個單個的物品消失了，但是同樣可以選擇同樣的數量!
_i.e._ $v_i \times 2^0 + v_i \times 2^1 = v_i \times 3$
但是最後記得補上沒辦法裝成2冪次的物品集，$v_i \times (c_i - 2 ^ {log_2 (c_i+1) - 1})$, $w_i \times (c_i - 2 ^ {log_2 (c_i+1) - 1})$。
複雜度: $O(W\sum log_2 c_i)$
```cpp=
for (int32_t i = 1; i <= n; ++i)
{
int32_t j = 0;
cin >> w >> v >> c;
while (c >= (1 << j))
{
V[idx] = v * (1 << j);
W[idx] = w * (1 << j);
c -= (1 << j);
++j;
++idx;
}
V[idx] = v * c;
W[idx] = w * c;
++idx;
}
```
練習題: [luogu P1776](https://www.luogu.org/problemnew/show/P1776)
---
#### 二維背包
> 給定n個物品，每種物品都有重量與價值，你最多可以拿 __M單位重的物品__ 以及 __L單位價值物品__，求最多可以選幾件。
>
其實基本思想一樣，只要再多開一維去轉移兩者就好。
```cpp=
for (int32_t i = 1; i <= n; ++i)
for (int32_t j = L; j >= v[i]; --j)
for (int32_t k = M; k >= w[i]; --k)
dp[j][k] = max(dp[j][k], dp[j - v[i]][k - w[i]] + 1);
```
練習題: [luogu P1855](https://www.luogu.com.cn/problem/P1855)
---
#### 超大背包
> 給定n個物品，每種物品都有重量與價值，你最多可以拿M單位重物品，求最大價值
> $M \leq 10^{15}, n \leq 40$
>
__!這題跟dp沒甚麼關係__
還記得一般背包的複雜度嗎: $O(nM)$
明顯的這裡根本不行用一般背包解。
我們應該利用$n$比較小的特性。
假設我們將物品分成兩組，那最優解一定是在第一組總共拿$v1, w1$、第二組則是$v2, w2$，且$w1 + w2 <= M$
枚舉拿第一組東西的所有情況成一集合$S$，然後再去枚舉第二組的情況，這樣看起來複雜度是$O(2^{\frac{n}{2} + 1})$，不算太差。
但是我們枚舉完第一組東西後，正在枚舉第二組時，還需要找到$S$中最大的$v$，且滿足$w\leq M-w_{now}$。
我們得先把第一組枚舉情況排序好，然後剔除掉$S_{vi} < S_{vj}$且$S_{wi} > S_{wj}$的$i$，在枚舉第二組時，二分搜$max\{S_{vi} ,S_{wi}\leq M-w_{now}\}$
__真正的複雜度:__ $O(2^{\frac{n}{2}}+2^{\frac{n}{2}} \times \frac{n}{2})$
練習題:
---
### 狀態壓縮DP
> 旅行員推銷問題(TSP):
> 給定n個城市以及m個道路，保證所有城市都連通，問從起點尋遍所有城市再回到起點的最短路徑。
>
如果你想dfs直接硬爆找解，複雜度是$O(n!)$
當$n=10$就已經很勉強了。
一般會使用位元dp去壓縮複雜度。
* 把每個點的狀態區分為0跟1，就能用一個整數的位元去表達一群狀態的集合
* 可以發現這樣就能簡單的儲存各狀態下的解了，因為一群狀態其實就是一個二進位的數，可以換成十進位的數當作dp的index
> 其實不一定要是0或1，也有3進位的狀態壓縮喔
$S$為走過的城市集合，而$v$是目前的位置
定義```dp[S][v]```為走過的集合且目前在v的位置，走完剩餘點，回到起點的最小路徑。
則轉移式為 $dp[s|a << u][u] = min\{dis(v, u) + dp[s][v], u \notin s\}$
```cpp=
for (int32_t i = 0; i < (1 << n); ++i)
fill(dp[i], dp[i] + n, INF);
dp[(1 << n) - 1][0] = 0;
for (int32_t S = (1 << n) - 2; S >= 0; --S)
{
for (int32_t v = 0; v < n; ++v)
for (int32_t u = 0; u < n; ++u)
if ((S & (1 << u)) == 0)
dp[S][v] = min(dp[S][v], dis(v, u) + dp[S | (1 << u)][u]);
}
ans = dp[0][0];
```
練習題: [tioj 1468](https://tioj.ck.tp.edu.tw/problems/1468)(三進位狀壓)
---
## 五、字串
### 術語解說
- substring
- subsequence
舉例：
"__Emiliatan__"是"__Emiliatan__ Maji Tenshi"的 __substring也是subsequence__
"__EMT__"是"__E__ miliatan __M__ aji __T__ enshi"的 __subsequence但不是substring__
### 當hash遇見string
> 有沒有可能用一個整數表達一個由小寫字母組成的字串呢？
不難想到就是把每個字符對照轉換，然後用26進位法做處理。
我們稱這種方法叫 __hash__，又稱 __哈希__、__雜湊__
但是我們的整數最大就是64位元，是不可能任意的轉換。
有什麼方法可以解決這樣的問題？
同餘可以處理這樣的問題。
但是在同餘下，每個數字就不會只代表一個字串。
不同的字串在hash後，代表同一數字我們稱為 __碰撞__
> 計算hash跟直接比較字串不是要花一樣的複雜度嗎？
- __rolling hash__
假設已知 $hash(Emiliata)=p$。
則$hash(Emiliatan)$顯然就是$p\times 26+'n'-'a'\pmod M$。
這種利用其他已知字串hash值求得新字串hash值的方法就是rolling hash。
（已知tan或sintan都可以用來求Emiliatan，請自己想）
- __處理碰撞__
當你遇到兩個hash值相同的字串時，有可能他們是同一字串，也可能不是，所以要逐一比對。
但是當兩字串hash值不同，那顯然不是同字串
- __減少非相同字串碰撞的機會__
- __選擇一個好的$M$__
在數論那一章節你會知道，當$M$是質數的時候，可以盡可能的「互質」。因此可以可以盡可能的讓每一個字串均勻的分佈到0~MOD-1上
- __做兩次hash__
一次不夠就兩次，選擇不同的MOD可以大大的降低碰撞的機率（這很顯然吧w）
- __複雜度分析__
因為rolling hash的緣故，求hash的複雜度可以被均攤，但是做模運算的常數很大（如果可以，用減法代替），也有碰撞的可能發生，因此分析碰撞的機率非常重要。
- __碰撞的機率分析__
如果出來的hash值分布是均勻的，且$M$是一個非常大的質數，差不多$10^{15}$，那麼相撞的機率是$10^{-15}$，機率小的幾乎不會發生。
> 但還是有方法可以構造出卡hash的測資......請小心
- hash在codeforce上的注意事項
在codeforce上，程式碼都會被看光光，所以當你要用hash時就要有被同房的hack爛的心裡準備。
他可以看你使用的MOD值輕鬆做出會不斷碰撞的字串卡死你。
hack別人的練習題：[zj c706](https://zerojudge.tw/ShowProblem?problemid=c706)
---
### 字串比對
> 給定一字串$A$，詢問字串$B$是否為$A$的substring。
>
- __Ctrl + F__
我開玩笑的。
- 複雜度: ~~看自己手速~~
- __暴力法__
一個個字元去比對$A$，失敗就挪動$B$再去比。
- 複雜度: $O(|A||B|)$
- __KMP Algorithm__
全名Knuth-Morris-Pratt Algorithm，學習這個演算法之前得先了解一些東西
- __prefix-suffix__
前綴等於後綴，稱作「相同前綴後綴」。一個字串通常有許多個「相同前綴後綴」。
_i.e._
abc -> {_null_, abc}
abcaa -> {_null_, a, abcaa}
abcabc -> {_null_, abc, abcabc}
ababa -> {_null_, a, aba, aba}
aaaaa -> {_null_, a, aa, aaa, aaaa, aaaaa}
abaabaa -> {_null_, a, abaa, abaabaa}
abzab -> {_null_, ab, abzab}
- __longest proper prefix-suffix__
一個字串的「最長的相同前綴後綴」就是原字串，「最短的相同前綴後綴」就是空字串，「次長的相同前綴後綴」就是第二長的相同前綴後綴。
_i.e._
abc -> _null_
abcaa -> a
abcabc -> abc
ababa -> aba
aaaaa -> aaaa
abaabaa -> abaa
abzab -> ab
- __failure function__
窮舉法的過程當中，當前比對成功的字串片段，是 P 的前綴。因為我們無法預測是 P 的哪幾個前綴，所以我們可以預先計算 P 的每一個前綴的「次長的相同前綴後綴」，以備不時之需。
failure function 是一個字串函數：輸入字串的其中一個前綴，則輸出該前綴的「次長的相同前綴後綴」。
input: __abzabc__
prefix | border |failure function| implementation
-------|--------|----------------|----------------
Ø | Ø | f(Ø) = Ø |
a | Ø | f(a) = Ø | failure[0] = -1
ab | Ø | f(ab) = Ø | failure[1] = -1
abz | Ø | f(abz) = Ø | failure[2] = -1
abza | a | f(abza) = a | failure[3] = 0
abzab | ab | f(abzab) = ab | failure[4] = 1
abzabc | Ø | f(abzabc) = Ø | failure[5] = -1
- A[0...i] 的「次長的相同前綴後綴」是 A[0...failure[i]]。
- failure[] 值為 -1 時，代表「次長的相同前綴後綴」為空字串。
- __code__
```cpp=
void failure_fuc(string &A)
{
for (int32_t i = 1, j = failure[0] = -1; i < A.size(); ++i)
{
while (j >= 0 && A[i] != A[j + 1])
j = failure[j];
if (A[j + 1] == A[i])
++j;
failure[i] = j;
}
}
```
__了解failure function最好的方法就是自己多試幾遍，試著在紙上寫幾個字串看看。__
- __KMP Algorithm__
終於可以講KMP的主體了。
有了failure function的幫助，我們可以很輕鬆的比對字串。
比對字串與構造failure幾乎一樣，只要遇見不符合的就一直移動。
```cpp=
void string_search(string &A, string &B)
{
failure_fuc(B);
for (int i = 0, j = -1; i < A.size(); ++i)
{
while (j >= 0 && A[i] != B[j + 1])
j = failure[j];
if (B[j + 1] == A[i])
++j;
if (j == B.size() - 1)
{
cout << "B starts at pos" << i - B.size() + 1 << endl;
j = failure[j];
}
}
}
```
下面練習題(cf 1326D2)的一點提示: 想想看failure function的定義、還有迴文顛倒後會有什麼性質?
> 練習題: [cf 1326D2](https://codeforces.com/contest/1326/problem/D2)
>
---
## 六、數論
### 同餘理論
- __模__
$a \mod b = q$, $q$滿足$a = b\times t+q$且$q < b$
_i.e_: $9 \mod 2=1$
- __同餘__
給定一正整數$m$，如果兩整數$a, b$滿足$a - b$可被$m$整除，則稱$a$與$b$對模$m$同餘。
- __模運算性質__
- 反身性: $a\equiv a \pmod m$
- 對稱性: $a\equiv b \pmod m$, 則$b\equiv a \pmod m$
- 傳遞性: 若$a\equiv b \pmod m$, $b\equiv c \pmod m$, 則$a\equiv c \pmod m$
- 同餘式相加/減/乘: 如同一般方程式
- 上述推導得: $a^k\equiv b^k \pmod m$
- 同餘式相除: 唯有定義下列運算，同餘式相除才有意義
$\frac{a}{b} \equiv x \pmod m$, $x$滿足$a \equiv bx \pmod m$
則$x\equiv ab^{-1} \pmod m$
$b^{-1}$為模$m$意義下的 __乘法反元素(inversion)__，或稱 __模逆元__
- $a\equiv b \pmod m$, 假設有一數$c$滿足$c|m$，則$a\equiv b \pmod c$
練習題: [zj c686](https://zerojudge.tw/ShowProblem?problemid=c686)(用到最後一個性質)
---
### 費馬小定理
> 任意質數$p$皆滿足 $a^{p-1}\equiv 1 \pmod p$
---
### 歐拉公式
~此公式為費馬小定理的推廣~
> 若$gcd(a,n)=1$ 則滿足$a^{\varphi(n)} \equiv 1 \pmod n$
!當$gcd(a,n)\neq1$時，另外有公式可以化簡指數（詳情請見intermediate level）
---
### 盧卡斯定理
> 設$n=sp+q, m=tp+r$，而$q,r\leq p$且$p$是質數。
> 有$C^{n}_{m} = C^{sp+q}_{tp+r} \equiv C^{s}_{t}C^{q}_{r} \pmod p$
>
---
### 擴展歐幾里得算法
英文稱exgcd，這大概是資訊中你唯一一個國小就會的東西，本質上就是輾轉相除法。
exgcd可以在求gcd(a, b)的同時求出滿足貝祖等式的x, y
> 貝祖等式: 對於$a, b, m$，$ax + by = m$
> 斐蜀定理: 對於$a, b, m$，$ax + by = m$有解，若且唯若$m=t \times gcd(a, b)$。
>
* 解法
* 實作
```cpp=
int32_t exgcd(int32_t a, int32_t b, int32_t& X, int32_t& Y)
{
if (b == 0)
{
X = 1, Y = 0;
return a;
}
int32_t r = exgcd(b, a % b, Y, X);
Y -= a / b * X;
return r;
}
```
練習題: [zj e320](https://zerojudge.tw/ShowProblem?problemid=e320)(斐蜀定理)
---
### 模逆元
> 已知$a, b$，求$ax \equiv 1 \pmod b$之$x$。
__!模逆元存在的條件是$gcd(a, b) = 1$__
__!只要模逆元存在，即有無限多個__
~可以用貝祖等式證證看~
* __exgcd求模逆元__
* 改寫: $ax + by = 1$
是不是跟上面的甚麼東西一樣阿?
現在你會求模逆元囉。
* 有時候題目會要求正整數模逆元，只要先求出$x$，再寫這行就好:
```cpp=
x = (x % b + b) %b;
```
* __歐拉定理求模逆元__
* 改寫 $a^{\varphi(b)} \equiv 1 \pmod b$ 成 $a \times a^{\varphi(b) - 1} \equiv 1 \pmod b$
$a$之模逆元即為$a^{\varphi(b) - 1}$
可用快速冪實做。
__!求單個模逆元可以用上面兩個方法__
* __遞推式模輸出對於1~p的所有模逆元。 $p \leq 10^6$__
* 遞推式: $i^{-1} = (b - \lfloor\dfrac{b}{i}\rfloor) \times (b \pmod i)^{-1} \pmod b$
* 推導過程:
設$t = \lfloor\dfrac{b}{i}\rfloor$, $k = b \pmod i$
則$t \times i + k \equiv 0 \pmod b$
使$k \equiv -t \times i \pmod b$
兩邊同除$i\times k$
得$i^{-1} \equiv -t\times k^{-1} \pmod b$
成$i^{-1} \equiv (b- \lfloor\dfrac{b}{i}\rfloor)\times (b \pmod i)^{-1} \pmod b$
- __逆元積性:__
> 對於$a, b$模$p$的逆元$a^{-1}, b^{-1}$，有$(ab)^{-1}\equiv a^{-1}b^{-1} \pmod p$
>
練習題: [zj a289](https://zerojudge.tw/ShowProblem?problemid=a289)(模板題),[zj e902](https://zerojudge.tw/ShowProblem?problemid=e902), [cf 696C](https://codeforces.com/contest/696/problem/C)
---
### 中國剩餘定理
> 韓信點兵: 有$n$種數法，每次數$b_i$個人，會剩下$r_i$個人。求最少有幾個人
* __遞推法__
$n$種數法的問題看起來很難，不妨先思考$n=2$的情況。
我們有以下算式
$\left\{ \begin{array}{rcl}
answer=b_1\times x_1+r_1 \\
answer=b_2\times x_2+r_2
\end{array}\right.$
可以整合成
$b_1\times x_1+r_1=b_2\times x_2+r_2$
$=> b_1\times x_1 - b_2 \times x_2 =r_2 - r_1$
這樣就能利用exgcd求出$x_1$和$x_2$進而還原出$answer$
至於$n$種數法就是從$2$一路推廣到$n$就好了，非常簡單
__複雜度__：$O(nlogC)$ ~C是值域~
* __構造法__
設$T = \prod b_i$, $T_i = \dfrac{T}{b_i}$。
設$M_i=$模$b_i$意義下$T_i$的模逆元。
答案即是$\sum M_i*T_i * r_i$
__複雜度__: $O(nlogC)$
__!此作法容易超出整數範圍。__
練習題: [zj d791](https://zerojudge.tw/ShowProblem?problemid=d791), [tioj 1459](https://tioj.ck.tp.edu.tw/problems/1459)
---
## 七、離線算法
> IOI的題目都會強制在線，不過等你當上國手再來擔心吧w
每當寫資料結構題時，有時候會需要寫一顆很複雜的結構，有沒有辦法避免呢?
實際上，操作可以離線做，每次詢問都不需要立即輸出答案，可以先把所有操作全部讀入，再來一次處理輸出答案。
這種想法可以大大避免極為複雜的資料結構。
下面將介紹幾種離線算法。
### 莫隊算法
> 給定一長度為$n$的數列，有$q$個詢問，問區間$l,r$內眾數出現幾次? 有幾個眾數?
> !可以離線
這題目乍看下是要刻一個比較特殊的線段樹，但是真的需要嗎?
首先，我們把問題reduce成
> 給定一長度為$n$的數列，有兩個索引$l,r$，有$q$個操作，使$l$變大或變小1、使$r$變大或變小1，問每次操作
區間$l,r$內眾數出現幾次? 有幾個眾數?
>
這個問題看起來就簡單多了。
設```app[x]```, ```cnt[c]```, ```maxcur```為$x$出現幾次、出現$c$次的有幾種數字、目前的眾數是出現幾次。
每次移動雙指標時，都去維護```app[x], cnt[c], maxcur```，
```cpp=
void sub(int x)
{
--cnt[app[x]];
--app[x];
++cnt[app[x]];
if (cnt[maxcur] == 0)
--maxcur;
}
void add(int x)
{
--cnt[app[x]];
++app[x];
++cnt[app[x]];
maxcur = max(maxcur, app[x]);
}
//~~
while(q--)
{
//~~
if (op == "L l")
add(arr[--l]); //左指標左移
else if (op == "L r")
sub(arr[l++]); //左指標右移
else if (op == "R l")
sub(arr[r--]); //右指標左移
else if (op == "R r")
add(arr[++r]); //右指標右移
cout << maxcur << ' ' << cnt[maxcur] << '\n';
}
```
這樣的複雜度是$O(q)$。完美解決。
但是這個問題跟原始問題比起來，差在一個 __移動是連續的__；一個是 __左界右界亂跳__。
那我們不妨讓原始題目的詢問左右界排序成連續的樣子。
依照左界大小將詢問排序，再依照剛剛的做法去做，但是這樣會有一個問題
> 右界怎麼辦?
如果有很多筆操作，左界都相同，但是右界差距極大，這樣複雜度最差是$O(n^2)$
有沒有一種辦法去同時把左界排序又能維護好右界遞增呢?
有，但是左右界都需要犧牲一點單調性。
利用分塊的思想，將$n$個元素切成$K$塊，接著將所有詢問按照$L_i$所在的區塊排序，如果在同一個區塊，就再對
$R_i$做排序。
- __複雜度分析__:
因為分塊的特性，在同一塊的左界不會移動超過$\frac{N}{K}$次，而左界屬於不同塊的操作，移動次數最多也不會超過N次。所以左界移動複雜度是$O(\frac{NQ}{K})$。
對於右界因為$R_i$是遞增，所以對於同一塊複雜度最多$O(N)$，對不同塊因為交界最多$K$次，每次最多也$O(N)$，所以維護右界複雜度為$O(NK)$。
取$K=\sqrt N$，複雜度為 $O(Q\sqrt N +N \sqrt N)$
- __奇偶優化__:
每一塊的$R_i$都是遞增，因此在遇到交界處時會有一個"大斷層"，導致右界必須移動許多次，但是如果反過來變成奇數塊遞增，而偶數塊遞減，就會讓右界的移動接近連續
實做判斷區塊是否為偶數進行遞增或遞減排序。
- __code:__
因為有點長，所以貼連結: [Mo's alogrithm](https://pastebin.com/sLbTNxmP)
練習題: [zj b417](https://zerojudge.tw/ShowProblem?problemid=b417)(模板題),[tioj 1699](https://tioj.ck.tp.edu.tw/problems/1699)
## 八、常數優化
> premature optimization is the root of all evil
* __編譯器優化__
```cpp
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC optimize("O3")
```
---
* __bitset__
1. all 測試此 bitset 中的所有位，以 __判斷它們是否全部都設為true__
2. any 判斷 __任何位元是否設為1__
3. count 回傳位元序列中 __位元1數量_
4. flip 反轉 bitset 中的所有位元值，或在指定位置反轉單一位元
5. none 判斷 __是否沒有已設為 1 的位元__
6. reset 將 bitset 中的所有位元重設為 0，或將指定位置的位元重設為 0
7. set 將 bitset 中的所有位元設為 1，或將指定位置的位元設為 1。
8. size 傳回 bitset 物件中的位元數
9. test 判斷指定位置的 __位元是否為 1__
10. to_string 將 bitset 物件轉換為字串表示
> 選訓時如果我會bitset就能多拿好多分數了......
## 九、計算幾何
計算幾何是競賽中很少出現，但是一旦出現高機率是難題。
通常牽涉到很多數學，_i.e._ 向量
### 基本數學知識
請至少具備高中的數學知識而且擁有把圖形座標化的技巧
外積、斜率、內積、行列式等等...
### 極角排序
- __實作:__
- atan2()
```cpp=
bool cmp(point& a,point& b)
{
return atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
}
```
- 判斷象限後用叉積判斷順序，極角相同再用長度判斷（視需求而定）
```cpp=
double cross(Point& a, Point& b)
{
return a.x * b.y - a.y * b.x;
}
bool cmp(Point& a, Point& b)
{
if (a.y == 0 && b.y == 0 && a.x * b.x <= 0) return a.x > b.x;
if (a.y == 0 && a.x >= 0 && b.y != 0) return true;
if (b.y == 0 && b.x >= 0 && a.y != 0) return false;
if (a.y * b.y < 0) return a.y > b.y;
double c = cross(a, b);
return c > 0 || c == 0 && fabs(a.x) < fabs(b.x);
}
```
atan2()有精度問題，cross版寫起來又繁瑣。
### 鞋帶公式
> 給定一多邊形的頂點座標$(x_1, y_1), (x_2, y_2)...$，求此多邊形面積?
一個很簡單的公式: $S = \frac{1}{2}|\sum_{i=1}^{n} x_iy_{i+1}-y_ix_{i+1}|$
其中$(x_{n+1}, y_{n+1})=(x_1,y_1)$
!注意這個公式必須先讓頂點座標呈 __順時針或逆時針順序__，且無論凸的多邊形或是凹的多邊形都可以用這個公式。
### 凸包
> 給定點集$S$，求能夠包覆住所有點的最小凸多邊形。
> 在這裡「凸」的定義為，多邊形內任意兩點連線不經過圖形外部。
>
- __Andrew's Monotone Chain__
如果我們觀察下凸包會發現他的斜率是遞增的，所以我們可以先將點集$S$按$x$排序，$y$為第二比較。
最左邊必然為凸包上一點，所以可以先將它加入一個容器。
我們現在要維護這個容器裡的點之斜率單調性，也就是說$slope(a_i,a_{i+1})<slope(a_{i+1},a_{i+2})$。
每次加入一個點，若剛剛的點不滿足上面的條件，就一直pop這個容器的head，
__直到上述條件滿足為止__。
看圖比較好理解。
__初始狀態__
__檢查第三點的正確性__: $slope(1,2)<slope(2,3)$
__檢查第四點__: 發現$slope(2,3)>slope(3,4)$，不符合維護的性質，將第三點pop掉。
__檢查第五點__: $slope(2,4)<slope(4,5)$
__檢查第六點__: 發現$slope(4,5)>slope(5,6)$，將第五點pop掉。同樣，$slope(2,4)>slope(4,6)$，將第四點pop掉。
這樣我們就找到了下凸包。
上凸包一樣可以用此策略去判斷，但須稍做修改，例如斜率單調的判斷，細節留給你們思考。
> 確定template有沒有寫對時，可以構造一個四個點的正方形當簡單的測資
練習題: [luogu P2742](https://www.luogu.com.cn/problem/P2742)
### 最近點對
> 給定點集$S$，求$S$中最近的兩個點
- 暴力法
任意的窮舉兩點
- 複雜度: $O(n^2)$
- 再優化
先讓點依照x軸排序，這樣就可以剪枝
- 最差複雜度: $O(n^2)$
在點是隨機的情況下，我們可以相信，每一次枚舉第二點，期望上都可以排除$\dfrac{n}{2}$個第一點的選擇。
因此我們有 __平均複雜度：$O(nlogn)$__
實際比賽上，這種作法通常會有特殊測資讓你TLE，不過我們可以先random旋轉整張圖片，讓這個作法也能AC。
- 分治法 （更詳細可以參考[演算法筆記](http://www.csie.ntnu.edu.tw/~u91029/Point2.html#3)）
我們可以畫一條把整張圖切成兩半，然後把答案分成「最近點對在左側」、「最近點對在右側」、「最近點對橫跨兩側」三種情形。先將左側與右側分別遞迴求解之後，再利用左側與右側的答案，快速算出橫跨兩側的答案。
- __Preprocessing__:
一、排序所有點，以$X$座標為主，$Y$座標無所謂。$O(NlogN)$
二、檢查是否有共點。如果有，就找出所有共點，演算法結束。$O(N)$
- __Divide__:
把所有點分為左右兩側，左側、右側的點數盡量一樣多。
- __Conquer__:
左側、右側分別遞迴求解。
- __Combine__:
利用左側、右側的最佳解$d$，求出橫跨兩側的解：
一、首先找出靠近中線的點，與中線的距離$\leq d$。$O(N)$
（小於d、不包含d，則只找出其中一組最近點對。）
二、排序這些點，Y座標為主，X座標為輔。O(NlogN)
三、每一個點都找其上方鄰近的點，看看能不能形成最近點對。
只需檢查至後三點。O(N⋅3) = O(N)
答案為左側、右側、橫跨兩側，三者當中的最佳解。
至於為何是檢查後三點呢？就留給讀者自行思考
### 最遠點對
> 給定點集$S$，求$S$中最遠的兩個點
- 旋轉卡尺
很顯然的，最遠點對一定在凸包上，然後呢？
如果距離A點最遠的點是D，那顯而易見的，距離B最遠的點就會是D,E或F。
你可以把最遠點對的選擇想像成一個two pointers然後，他們會順時針或逆時針的轉。
那我們就可以枚舉其中一個pointer，然後另一個pointer只要跟著轉就可以在O(n)下找到凸包的最遠點對。
> 另一個pointer要不要轉？
最簡單的作法就是直接算出距離來決定要不要轉。但這樣常數有點大。
所以可以用向量的作法
這很好想，如果D到A的距離大於E到A，那依照底乘以高這個公式可以觀察到$\Delta ABD$的面積大於$\Delta ABE$。
因此只要用向量算兩三角形的面積就能決定要不要轉了。
---
## 寫完心得
在這裡感謝ioic的講義，以及所有我問過的大神、找過資料的blog、OI wiki、還有一堆題目的出題者。
一開始僅有的第一行我還記得一清二楚，"嘉中資訊講義"，一直到這裡已經增加到1370行了。(4.14.20更新: 1534行) (4.15.20更新: 1688行)
希望後人們都可以靠這份講義上1!、2!、甚至國手，__looking forward to the day.__
Sign in with Wallet
Connect another wallet