嘉中資訊科培訓講義(elementary level)

作者：vincent97198、エミリア

嘉中資訊科培訓講義(elementary level)

零、概論

Online Judge

主要競賽

複雜度

前國手們的建議

一、基礎演算法與技巧整理

Greedy

二分搜

三分搜

打表

本地爆搜

時間剪枝

二、資料結構

線段樹

Sparse Table

BIT 這是エミリア最喜歡的資料結構之一。

treap 同樣是エミリア最喜歡的資料結構之一

三、圖論

專業術語

樹

一般圖的連通性

四、DP 這是エミリア最討厭的東西

背包

狀態壓縮DP

五、字串

術語解說

當hash遇見string

字串比對

六、數論

同餘理論

費馬小定理

歐拉公式

盧卡斯定理

擴展歐幾里得算法

模逆元

中國剩餘定理

七、離線算法

莫隊算法

八、常數優化

九、計算幾何

基本數學知識

極角排序

鞋帶公式

凸包

最近點對

最遠點對

寫完心得

這些都學過了，讓我離開新手村!

零、概論

我相信會用到這個題單的人，已經解完基礎的題單了><
所以接下來的內容，會省略掉我認為你們應該會的東西，然後多做一些補充。

這是一份花了幾天、犧牲考試成績等價交換出來的講義，好好珍惜。

練習題有時候會需要已經教過但非該章的知識，請自行思考。

Online Judge

UVa, Atcoder, codeforces, TIOJ, POJ, Luogu

主要競賽

請多打線上比賽，友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 (l o g n)$ , modify is
  $O (l o g n)$
  sort is
  $O (n l o g n)$
  lower/upper_bound is
  $O (l o g n)$
  floyd warshall is
  $O (V^{3})$
  Dijkstra is
  $O ((V + E) l o g V)$
  set.count() is
  $O (l o g 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 (l o g n)$

練習題: poj 3685, zj c904, zj c575

三分搜

用法
三分搜尋法和我們熟悉的二分搜尋法在實做層面上，算是差不多的東西，唯一不同的地方在於
- 二分搜尋法用於 尋找單調函數的某個值
- 三分搜尋法則是用於 尋找n次函數的某個值
  
  須確定搜索的範圍內函數的形狀是U或∩才行
原理
假定要拿來解釋的這個是要找二次函數的極小值，且極值的位置在左右界內僅靠一個參考點無法得知，該點的左右何者較接近極小值，但若有2個參考點（也就是三等份）就能得知較小的點必定比另一點更靠近極小值（二次函數性質），就能因此鬆弛解的範圍

實作 (U型函數)
```
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 (l o g n)$

練習題: AtCoder Beginner Contest 130 pF

打表

有的時候題目的形質非常神秘，不易觀察（尤其是數學題(~~玄學題~~）)
我建議可以本地打表，觀察性質，可能會有助於思考(吧

練習題: zj e320, cf 1342C

本地爆搜

本地算完答案或一些關鍵數字，藉此壓縮複雜度。
（面對難題或許有奇效 ~~通常沒有~~）

練習題: zj e299

時間剪枝

快要TLE時，不管答案是否最優，直接輸出答案。
或是搜什麼東西，結果時間快到了還搜不到，直接輸出不存在。

(喇分還是挺有效的。)

二、資料結構

工欲善其事，必先利其器

線段樹

大概是資料結構的新手技能吧。 _{沒有人不會的。}

生來就是解決區間問題。

給定一長度為n的數列，求區間
$l, r$ 的最大/小值、和。

原理
將一段數列，分治處理，利用分治的技巧，整個線段最多被切割
$l o g n$ 次。藉此可以很快的維護線段的查詢、修改。
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, luogu P1438

Sparse Table

又稱稀疏表。很少用到。
只能用在RMQ(Range Minimum/Maximum Query)，不能算區間和。

原理
與許多資料結構的想法一樣，先處理小部分，在合併成整體。
定義Table[i][j]為，在索引值i處，長度為
$2^{j}$ 的數列最大/小或和，甚至乘。

build:
$O (n l o g n)$
query:
$O (1)$
modify: it can't be modified
使用時機
不需要修改，大量尋找區間極值時。
但是很少會用到，但是一旦用到絕對比刻一顆線段樹還快很多。

實做
build:
先預處理長度為1的段。



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:


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 - l o w b i t (x), x]

的區間和。
(如果你還是不懂，可以畫圖看看)

那 單點修改 就是


for (int32_t i = pos; i <= maxn; i += lowbit(i))
    bit[i] += value;

前綴查詢:


for (int32_t i = pos; i; i -= lowbit(i))
    res += bit[i];

如果將元素的值當作下標；且在下標處+1的話，可以擴展使用下面的功能
第k小查詢:

錯誤範例複雜度：

O (l o g^{2} n)











//錯誤範例
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 (l o g n)






//正確範例
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 (l o g n)$
query:
$O (l o g n)$
使用頻率
不算很低，也不算很高，但是很方便，算是輕便型segment tree
優點
常數很小、coding複雜度小

練習題: tioj 1282, zj b577, zj 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:











struct Treap
{
    Treap *l, *r;
    int32_t key, pri;
    Treap(int32_t _key)
    {
        l = r = nullptr;
        key = _key;
        pri = rand();
    }
}

merge:














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:




















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:






void insert(Treap *t, int32_t k)
{
    Treap *lt, *rt;
    split(t, k, lt, rt);
    merge(merge(lt, new Treap(k)), tr);
}

remove:







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了。








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:















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:


//與上面唯一有差別的只有當某顆treap的結構改變時，需要呼叫pull()去更新資訊
//例如 呼叫完split()後

merge:


//與上面唯一有差別的只有當某顆treap的結構改變時，需要呼叫pull()去更新資訊
//例如 呼叫完merge()後

kth: (第k小)







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即可。
















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: (改)




















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:



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，可以降低系統分配記憶體的開銷。

區間加值:








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: (改)























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: (改)






















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(模板), cf 702F

三、圖論

資訊的圖是由 點(vertex) 邊(edge) 構成的。

圖有下面幾種:

有向圖 : 邊有方向性
無向圖 : 邊無方向性
簡單圖 : 無重邊、無自環
完全圖 : 所有點彼此互連
二分圖 : 把圖分成兩部分，同一個集合裡的點 彼此不相連，且圖上不存在奇環

專業術語

$D A G$ : 有向無環圖
$| V |$ : 點的個數
$| E |$ : 邊的個數

樹

圖論中的樹，指的是有

n

個點、

n - 1

條邊，每個點都相連通的圖。

樹直徑

要求兩端點
$i$ ,
$j$ 使得
$d i s (i, j)$ 為樹中最大，求
$i$ ,
$j$ ,
$d i s (i, j)$ ，

有DP、兩種dfs作法，這裡只介紹dfs。

兩次dfs作法
隨機一頂點找最遠點v，再由v去找離v最遠的點u，則(u,v)為樹直徑兩端，直覺無比皆大歡喜。


        // 沒有code啦，難道dfs也不會？

一次dfs作法
樹dp





















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)

給定
$r o o t, a, b$ ，有
$Q$ 個詢問求
$a, b$ 的共同祖先
$c$ ，且
$c$ 距離兩者皆最小。

naive解
dfs一遍，確定每個點的父親以及深度，然後從
$a, b$ 往上爬到同樣的節點即可。
- 複雜度:
  $O (Q n)$

倍增法
從剛剛的naive解我們會發現我們每次都只是往上走 1 而已，何不走大步一點呢?
如果每次我們都走2的冪次步的話，可以走到任意祖先。 (二進制的性質)
那我們就預處理每個點往上走

2^{j}

步會到誰就好了。
當詢問時，就開始跳，直到相同的點。


























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);
    }
}
































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 (l o g N)

dfs序

給定一棵樹及根，上面有
$n$ 個節點，每個節點都有一顏色
$c_{i}$ ，總共有
$m$ 個操作，有兩種操作:

將
$v$ 的子樹染色成
$k$

詢問
$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 + s i z e - 1

)。

至此，我們只需要一次dfs找序號，用一支援區間OR的資料結構即可解決問題。

一些樹上問題可以透過dfs序解決，當然也需要點巧思才能將問題轉化。
例如

給定一棵樹一個根，總共
$n$ 個點，有
$q$ 個查詢，問
$i$ 是不是
$j$ 的祖先

如果只單看進入時間根本看不出來，一個不夠? 那就看兩個。
連同 離開時間 一起看。
細節自己想想，這邊不多贅述。

本章練習題: USACO 2019.12 Platinum Bessie's Snow Cow, cf 620E

一般圖的連通性

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

，

l o w (v)

被定義為在不透過父邊，能夠到達的最低祖先的深度

!上圖的節點4可以走到2，所以

l o w (4) = 1

；節點7可以走到1，所以

l o w (7) = 0

，而3可以通過4走到2，所以

l o w (3) = l o w (4) = 1

，其餘相同。

可以發現當

l o w (v)

與

d e p (v)

一樣時，

e = {v, f a (v)}

為橋。

實作:























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

就都是邊雙分量。
































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

的

d e p t h (v) \leq l o w (u)

，則節點

v

必為割點。

!但是root需要特判

























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解







































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































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, cf 1220E

四、DP _{這是エミリア最討厭的東西}

背包

算是DP入門的新手技，但是有許多變體。

完全背包

給定n個物品，每種物品都有重量與價值，且每種物品有無限個，你最多可以拿M單位重物品，求最大價值

code:



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

多重背包

給定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^{l o g_{2} (c_{i} + 1) - 1})

w_{i} \times (c_{i} - 2^{l o g_{2} (c_{i} + 1) - 1})

。

複雜度:

O (W \sum l o g_{2} c_{i})


















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

二維背包

給定n個物品，每種物品都有重量與價值，你最多可以拿 M單位重的物品 以及 L單位價值物品，求最多可以選幾件。

其實基本思想一樣，只要再多開一維去轉移兩者就好。




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

超大背包

給定n個物品，每種物品都有重量與價值，你最多可以拿M單位重物品，求最大價值

$M \leq 10^{15}, n \leq 40$

!這題跟dp沒甚麼關係

還記得一般背包的複雜度嗎:

O (n M)

明顯的這裡根本不行用一般背包解。
我們應該利用

n

比較小的特性。

假設我們將物品分成兩組，那最優解一定是在第一組總共拿

v 1, w 1

、第二組則是

v 2, w 2

，且

w 1 + w 2 <= M

枚舉拿第一組東西的所有情況成一集合

S

，然後再去枚舉第二組的情況，這樣看起來複雜度是

O (2^{\frac{n}{2} + 1})

，不算太差。

但是我們枚舉完第一組東西後，正在枚舉第二組時，還需要找到

S

中最大的

v

，且滿足

w \leq M - w_{n o w}

。
我們得先把第一組枚舉情況排序好，然後剔除掉

S_{v i} < S_{v j}

且

S_{w i} > S_{w j}

的

i

，在枚舉第二組時，二分搜

m a x {S_{v i}, S_{w i} \leq M - w_{n o w}}

真正的複雜度:

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的位置，走完剩餘點，回到起點的最小路徑。

則轉移式為

d p [s | a << u] [u] = m i n {d i s (v, u) + d p [s] [v], u \notin s}













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(三進位狀壓)

五、字串

術語解說

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
假設已知
$h a s h (E m i l i a t a) = p$ 。
則
$h a s h (E m i l i a t a n)$ 顯然就是
$p \times 26 +^{'} n^{'} -^{'} a^{'} (\mod 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

字串比對

給定一字串
$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













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幾乎一樣，只要遇見不符合的就一直移動。




















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

六、數論

同餘理論

模

$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 (\mod m)$
- 對稱性:
  $a \equiv b (\mod m)$ , 則
  $b \equiv a (\mod m)$
- 傳遞性: 若
  $a \equiv b (\mod m)$ ,
  $b \equiv c (\mod m)$ , 則
  $a \equiv c (\mod m)$
- 同餘式相加/減/乘: 如同一般方程式
- 上述推導得:
  $a^{k} \equiv b^{k} (\mod m)$
- 同餘式相除: 唯有定義下列運算，同餘式相除才有意義
  
  $\frac{a}{b} \equiv x (\mod m)$ ,
  $x$ 滿足
  $a \equiv b x (\mod m)$
  則
  $x \equiv a b^{- 1} (\mod m)$
  
  $b^{- 1}$ 為模
  $m$ 意義下的 乘法反元素(inversion)，或稱 模逆元
- $a \equiv b (\mod m)$ , 假設有一數
  $c$ 滿足
  $c | m$ ，則
  $a \equiv b (\mod c)$

練習題: zj c686(用到最後一個性質)

費馬小定理

任意質數
$p$ 皆滿足
$a^{p - 1} \equiv 1 (\mod p)$

歐拉公式

_{此公式為費馬小定理的推廣}

若
$g c d (a, n) = 1$ 則滿足
$a^{φ (n)} \equiv 1 (\mod n)$

!當

g c d (a, n) \neq 1

時，另外有公式可以化簡指數（詳情請見intermediate level）

盧卡斯定理

設
$n = s p + q, m = t p + r$ ，而
$q, r \leq p$ 且
$p$ 是質數。
有
$C_{m}^{n} = C_{t p + r}^{s p + q} \equiv C_{t}^{s} C_{r}^{q} (\mod p)$

擴展歐幾里得算法

英文稱exgcd，這大概是資訊中你唯一一個國小就會的東西，本質上就是輾轉相除法。
exgcd可以在求gcd(a, b)的同時求出滿足貝祖等式的x, y

貝祖等式: 對於
$a, b, m$ ，
$a x + b y = m$
斐蜀定理: 對於
$a, b, m$ ，
$a x + b y = m$ 有解，若且唯若
$m = t \times g c d (a, b)$ 。

解法

實作











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(斐蜀定理)

模逆元

已知
$a, b$ ，求
$a x \equiv 1 (\mod b)$ 之
$x$ 。

!模逆元存在的條件是

$g c d (a, b) = 1$
!只要模逆元存在，即有無限多個
_{可以用貝祖等式證證看}

exgcd求模逆元
- 改寫:
  $a x + b y = 1$
  是不是跟上面的甚麼東西一樣阿?
  現在你會求模逆元囉。
- 有時候題目會要求正整數模逆元，只要先求出
  $x$ ，再寫這行就好:
```
x = (x % b + b) %b;
```
歐拉定理求模逆元
- 改寫
  $a^{φ (b)} \equiv 1 (\mod b)$ 成
  $a \times a^{φ (b) - 1} \equiv 1 (\mod b)$
  
  $a$ 之模逆元即為
  $a^{φ (b) - 1}$
可用快速冪實做。

!求單個模逆元可以用上面兩個方法

遞推式模輸出對於1~p的所有模逆元。
$p \leq 10^{6}$
- 遞推式:
  $i^{- 1} = (b - ⌊ \frac{b}{i} ⌋) \times (b (\mod i))^{- 1} (\mod b)$
- 推導過程:
  設
  $t = ⌊ \frac{b}{i} ⌋$ ,
  $k = b (\mod i)$
  則
  $t \times i + k \equiv 0 (\mod b)$
  使
  $k \equiv - t \times i (\mod b)$
  兩邊同除
  $i \times k$
  得
  $i^{- 1} \equiv - t \times k^{- 1} (\mod b)$
  成
  $i^{- 1} \equiv (b - ⌊ \frac{b}{i} ⌋) \times (b (\mod i))^{- 1} (\mod b)$

逆元積性:

對於
$a, b$ 模
$p$ 的逆元
$a^{- 1}, b^{- 1}$ ，有
$(a b)^{- 1} \equiv a^{- 1} b^{- 1} (\mod p)$

練習題: zj a289(模板題),zj e902, cf 696C

中國剩餘定理

韓信點兵: 有
$n$ 種數法，每次數
$b_{i}$ 個人，會剩下
$r_{i}$ 個人。求最少有幾個人

遞推法

$n$ 種數法的問題看起來很難，不妨先思考
$n = 2$ 的情況。
我們有以下算式

${\begin{array}{rcl} a n s w e r = b_{1} \times x_{1} + r_{1} \\ a n s w e r = b_{2} \times x_{2} + r_{2} \end{array}$
可以整合成

$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}$ 進而還原出
$a n s w e r$
至於
$n$ 種數法就是從
$2$ 一路推廣到
$n$ 就好了，非常簡單

複雜度：
$O (n l o g C)$ _C是值域
構造法
設
$T = \prod b_{i}$ ,
$T_{i} = \frac{T}{b_{i}}$ 。
設
$M_{i} =$ 模
$b_{i}$ 意義下
$T_{i}$ 的模逆元。
答案即是
$\sum M_{i} * T_{i} * r_{i}$

複雜度:
$O (n l o g C)$

!此作法容易超出整數範圍。

練習題: zj d791, tioj 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，


































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{N Q}{K})$ 。
對於右界因為
$R_{i}$ 是遞增，所以對於同一塊複雜度最多
$O (N)$ ，對不同塊因為交界最多
$K$ 次，每次最多也
$O (N)$ ，所以維護右界複雜度為
$O (N K)$ 。
取
$K = \sqrt{N}$ ，複雜度為
$O (Q \sqrt{N} + N \sqrt{N})$
奇偶優化:
每一塊的
$R_{i}$ 都是遞增，因此在遇到交界處時會有一個"大斷層"，導致右界必須移動許多次，但是如果反過來變成奇數塊遞增，而偶數塊遞減，就會讓右界的移動接近連續
實做判斷區塊是否為偶數進行遞增或遞減排序。
code:
因為有點長，所以貼連結: Mo's alogrithm

練習題: zj b417(模板題),tioj 1699

八、常數優化

premature optimization is the root of all evil

編譯器優化

#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()




bool cmp(point& a,point& b)  
{  
    return atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
}

判斷象限後用叉積判斷順序，極角相同再用長度判斷（視需求而定）














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_{i} y_{i + 1} - y_{i} x_{i + 1} |

其中

(x_{n + 1}, y_{n + 1}) = (x_{1}, y_{1})

!注意這個公式必須先讓頂點座標呈 順時針或逆時針順序，且無論凸的多邊形或是凹的多邊形都可以用這個公式。

凸包

給定點集
$S$ ，求能夠包覆住所有點的最小凸多邊形。
在這裡「凸」的定義為，多邊形內任意兩點連線不經過圖形外部。

Andrew's Monotone Chain
如果我們觀察下凸包會發現他的斜率是遞增的，所以我們可以先將點集
$S$ 按
$x$ 排序，
$y$ 為第二比較。
最左邊必然為凸包上一點，所以可以先將它加入一個容器。
我們現在要維護這個容器裡的點之斜率單調性，也就是說
$s l o p e (a_{i}, a_{i + 1}) < s l o p e (a_{i + 1}, a_{i + 2})$ 。
每次加入一個點，若剛剛的點不滿足上面的條件，就一直pop這個容器的head，
直到上述條件滿足為止。

看圖比較好理解。

初始狀態

檢查第三點的正確性:
$s l o p e (1, 2) < s l o p e (2, 3)$

檢查第四點: 發現
$s l o p e (2, 3) > s l o p e (3, 4)$ ，不符合維護的性質，將第三點pop掉。

檢查第五點:
$s l o p e (2, 4) < s l o p e (4, 5)$

檢查第六點: 發現
$s l o p e (4, 5) > s l o p e (5, 6)$ ，將第五點pop掉。同樣，
$s l o p e (2, 4) > s l o p e (4, 6)$ ，將第四點pop掉。

這樣我們就找到了下凸包。
上凸包一樣可以用此策略去判斷，但須稍做修改，例如斜率單調的判斷，細節留給你們思考。

確定template有沒有寫對時，可以構造一個四個點的正方形當簡單的測資

練習題: luogu P2742

最遠點對

給定點集
$S$ ，求
$S$ 中最遠的兩個點

旋轉卡尺
很顯然的，最遠點對一定在凸包上，然後呢？

如果距離A點最遠的點是D，那顯而易見的，距離B最遠的點就會是D,E或F。
你可以把最遠點對的選擇想像成一個two pointers然後，他們會順時針或逆時針的轉。
那我們就可以枚舉其中一個pointer，然後另一個pointer只要跟著轉就可以在O(n)下找到凸包的最遠點對。

另一個pointer要不要轉？

最簡單的作法就是直接算出距離來決定要不要轉。但這樣常數有點大。

所以可以用向量的作法
這很好想，如果D到A的距離大於E到A，那依照底乘以高這個公式可以觀察到
$Δ A B D$ 的面積大於
$Δ A B E$ 。
因此只要用向量算兩三角形的面積就能決定要不要轉了。

寫完心得

在這裡感謝ioic的講義，以及所有我問過的大神、找過資料的blog、OI wiki、還有一堆題目的出題者。

一開始僅有的第一行我還記得一清二楚，"嘉中資訊講義"，一直到這裡已經增加到1370行了。(4.14.20更新: 1534行) (4.15.20更新: 1688行)
希望後人們都可以靠這份講義上1!、2!、甚至國手，looking forward to the day.