---
# System prepended metadata

title: PCCU 營隊筆記
tags: [演算法]

---


# PCCU 營隊筆記
&emsp;
---
# Day 1 圖論
## 1. 並查集
### [TIOJ  1312 . 家族](https://tioj.ck.tp.edu.tw/problems/1312) (裸題)
```csharp=
#include <iostream>
#define ll long long
using namespace std;

ll boss[10001];

ll find_boss(ll x);
void join(ll a, ll b);
int main()
{
    ll n, m, a, b, k, bossa, bossb;
    while (cin >> n >> m) {
        for (ll i = 1; i <= n; i++)
            boss[i] = i;

        for (ll i = 0; i < m; i++) {
            cin >> a >> b;
            bossa = find_boss(a);
            bossb = find_boss(b);
            join(bossa, bossb);
        }
        cin >> k;
        cout << find_boss(k) << endl;
    }

}

ll find_boss(ll x)
{
    if (boss[x] == x)
        return x;
    else 
        return boss[x] = find_boss(boss[x]);   
}

void join(ll a, ll b)
{
    if (a == b) return;

    if (a > b) {
        join(b, a);
        return;
    }

    boss[b] = a;
}
```
&emsp;
## 2. LCA (lowest common ancestor)
### [ZG_d767. 血緣關係](https://zerojudge.tw/ShowProblem?problemid=d767)
### <法一> 建立倍增表 ( 建立: O(n * log(n)、查詢: O( log(n) )
```csharp=
// 只留 LCA 模板

ll parents[300001], actr[25][300001], depths[300001] = {0};
vector<ll> childs[300001];
ll n, q;

void dfs(const ll &x, const ll &fa)
{
    depths[x] = depths[fa] + 1;
    actr[0][x] = fa;                    // ancestor == actr 

    for (ll child : childs[x]) {
        dfs(child, x);
    }
}

void make_dir(const ll &root)
{
    dfs(root, 0);

    for (ll i = 1; i < log2(n); i++)    
        for (ll j = 1; j <= n; j++) 
            actr[i][j] = actr[i - 1][actr[i - 1][j]];  
}

pair<ll, ll> LAS(const ll &root, ll a , ll b)
{
    ll kin_degree = 0;

    if (depths[a] < depths[b]) {
        return LAS(root, b, a);
    }

    ll step = depths[a] - depths[b];
    for (ll i = 0; i < log2(step) + 1; i++){
        if (step >> i & 1) {
            a = actr[i][a];
            kin_degree += pow(2, i);
        }
    }

    if (a == b)  // 不要忘了當 a 跳到與 b 同高時，a 有可能等於 b
        return { a, kin_degree };
         
    for (ll jump = log2(n); jump >= 0 ; jump--) {
        if (actr[jump][a] != actr[jump][b]) {
            a = actr[jump][a];
            b = actr[jump][b];
            kin_degree += pow(2, jump)* 2;
        }
    }

    return { actr[0][a], kin_degree  + 2};
}
```
:::info
(知識點1) **建立倍增表的 LCA 想法**

* 此種 LCA作法分為 2 個重要步驟: **1. 建立倍增表** 及 **2.求 LCA** 

1.  建立倍增表: **(定義倍增表 actr[ i ][ j ] 為第 j 點往上走 2^i 格的終點 )**

    **1. dfs :**　
    　　沒錯，建立倍增表前要先 dfs 圖形一遍。過程中我們要取得 <u>每點的深度 及 父節點值</u>
    2. **make_dir:**　
    　　dfs 圖形過後，我們將利用 <u>actr[i][j] = actr[i - 1][actr[i - 1][j]]</u> 關係式 ( 參 54~56 行 )，<u>由近到遠地 設定每一個節點的祖先</u>。這個祖先的關係即是所謂的倍增表



2. 求 LCA: 

   **1. 將 2 點拉到同一距離 :**:
   　　注意看 code: 67 ~ 73 行，你會發現它有 **if (step >> i & 1)** 的迴圈判斷式。沒錯，它用了**位元運算**去處理來判斷 2^i 要不要走，這個概念可以用以下圖表來呈現: 
     
     ![](https://i.imgur.com/fdFSG12.png =40%x) 
     
    由 圖中可以看到當我們將數字轉為二進位表示時，我們可以造出 0、1、0、1 的數據結構，這樣的結構使我們能用  "<u> & 1 (與 1 做位元運算的方式</u>" 一一對應出 2^0 、2^1 等值。而這些值相加即為 step 值 ( 其實就是**將值由 2 的冪次分解開來，再一一運算**)

   **2. 用跳跳二分搜的概念求得 LCA :**
   　　注意看 code: 78 ~ 84 行，只要看出 **actr[i][j] 的 i 代表 J 移動 2 ^ i 步**，你就會發現 <u>跳跳二分搜的概念</u>。剩下的就用此概念去想即可


    
 
:::
:::warning
* 因為此題丟了很多 queries，所以很不幸地，O( log(n) * n) 的想法會吃 TLE
:::
### <法一之二> 樹壓平 + 倍增法 (實作上更快)
```csharp=
void makeactr(ll x)  // 邊建立 ancestor 的同時邊樹壓平 (快多了)
{
    euler[t] = x;
    in[x] = t++;

    dep[x] = dep[fa[x]] + 1;

    ll p = fa[x];
    for (ll jump = 0; jump < (ll)(log2(n) + 1); jump++)
        actr[x][jump] = p, p = actr[p][jump];

    for (ll c : tree[x])
        makeactr(c);

    euler[t] = x;
    out[x] = t++;
}


bool isactr(ll actr, ll b)  // 用樹壓平的結果來判斷 a 是否是 b 的祖先
{
    if (in[actr] <= in[b] && out[b] <= out[actr])
        return true;
    return false;
}


ll lca(ll a, ll b)
{
    if (dep[a] > dep[b])
        return lca(b, a);

    if (isactr(a, b))
        return a;
    if (isactr(b, a))
        return b;
                                 // 對答案二分搜的概念
    for (ll jump = 21; jump > 0; jump /= 2)
        while (!isactr(actr[a][jump], b)) 
            a = actr[a][jump];

    return actr[a][0];
}
```
:::success
* 神奇的是這行
```csharp=
    for (ll jump = 21; jump > 0; jump /= 2)
        while (!isactr(actr[a][jump], b)) 
            a = actr[a][jump];
```
* 本身 jump 就是 倍增法 ( O(log(n) )，再加上 二分搜，這個寫法的複雜度逼近 O( log(n)^2 )。要這樣才會過這題 ==
:::

### <法二> 樹壓平 ( O(n) ) + 線段樹 <找最小值> ( 建立: O(n)、 查詢: O(log(n) )
```csharp=
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#define ll long long
#define pll pair<ll, ll>
using namespace std;

ll n, q;
vector<ll> childs[300001];
ll parents[300001] = {0};

pll euler[900000];
ll out[300001], t = 0;

struct Node
{
    ll L, R;
    pll mini;
};

Node* seg;

void dfs(const ll& depth, const ll& x);
void build(const ll& l, const ll& r, const ll& v = 1);
pll query(const ll& l, const ll& r, const ll& v = 1);
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    ll child, a, b, root, actr, dep;
    cin >> n >> q;
    for (ll i = 1; i <= n; i++) {
        cin >> child;
        while (child != 0) {
            childs[i].emplace_back(child);
            parents[child] = i;
            cin >> child;
        }
    }

    for (ll i = 1; i <= n; i++)
        if (parents[i] == 0)
            root = i;

    dfs(0, root);
    seg = new Node [t << 2 | 1];
    build(0, t - 1);

    for (ll i = 0; i < q; i++) 
    {
        cin >> a >> b;

        if (out[a] <= out[b])
            tie(dep, actr) = query(out[a], out[b]);
        else
            tie(dep, actr) = query(out[b], out[a]);

        cout << actr << ' ' << euler[out[a]].first + euler[out[b]].first - 2 * dep << endl;
 
    }
}

void dfs(const ll& depth, const ll& x)
{
    euler[t++] = { depth, x };
    
    for (ll child : childs[x])
    {
        dfs(depth + 1, child);
        euler[t++] = { depth, x };
    }

    out[x] = t - 1;
}

void build(const ll& l , const ll& r, const ll& v)
{
    ll mid = (l + r) >> 1;
    seg[v].L = l;
    seg[v].R = r;

    if (l == r) {
        seg[v].mini = euler[r];
        return;
    }

    build(l, mid, v << 1);
    build(mid + 1, r, v << 1 | 1);
    seg[v].mini = min(seg[v << 1].mini, seg[v << 1 | 1].mini);
}

pll query(const ll& l, const ll& r, const ll& v)
{
    ll mid = (seg[v].L + seg[v].R) >> 1;

    if (seg[v].L == l && seg[v].R == r) 
        return seg[v].mini;
    else if (r <= mid)
        return query(l, r, v << 1);
    else if (l > mid)
        return query(l, r, v << 1 | 1);
    else
        return min(query(l, mid, v << 1), query(mid + 1, r, v << 1 | 1));
}
```
:::warning
* 最後一筆測資 ( TLE )
:::
---
&emsp;
# Day 2 字串

## １. KMP 演算法

### [f416. 果然我的期中程設考搞錯了什麼](https://zerojudge.tw/ShowProblem?problemid=f416)
```csharp=
// 只留演算法

void make_next(string stra)
{
    ll ai = 0, aj = 1;

    while (aj < stra.length())
    {
        if (stra[ai] == stra[aj]) {
            next_[aj] = ai + 1;
            ai++;
            aj++;
        }
        else if (stra[ai] != stra[aj] && ai == 0) {
            aj++;
        }
        else {
            ai = next_[ai - 1];
        }
    }
}

ll KMP(string stra , string strb)
{

    ll times = 0, ai = 0, bi = 0;
    
    while (bi < strb.length())
    {
        if (stra[ai] == strb[bi]) {
            ai++;
            bi++;
        }
        else if (stra[ai] != strb[bi] && ai == 0) {
            bi++;
        }
        else 
            ai = next_[ai - 1];
        
        if (ai == stra.length()) {
            bi = bi - ai + 1;
            ai = 0;
            times++;
        }
    }

    return times;
}
```
:::info
(知識點) **KMP 演算法** ( Knuth-Morris-Pratt  algorithm )

* 了解 KMP，要先了解 "**為甚麼暴力解的做法不好**"，這樣我們才知道怎麼 "**減少重複的計算**"

* 所以 為甚麼暴力解的做法不好? (搭配 [之乎-阮行止的說明](https://www.zhihu.com/question/21923021/answer/281346746)):

  觀察暴力解的情形可以發現，有些時候，模式串會如下圖一樣，明明已經比較到最後一個數值 B 了，卻很不幸地在最後 "因為不相等而重新來過"。
  　　當這種情況發生時，模式串會"**不長進地**" 往下掉一位 再重新計算。為甚麼我會說他不長進呢?　因為他明明**有上一回合的資訊**，卻放著不用、硬是呆呆地重來計算，當然不長進!

   ![](https://i.imgur.com/1uvXN9w.png)



* 於是乎為了利用上一回合的資訊 (及減少無謂的計算)，我們有了個想法 --- 如果每次跳過不可能有答案的區域，是否就能減少計算? 
( 可以想一下**為甚麼以下 2 個模式串會被跳過** (被打 xx 了)，這隱含著做部分匹配表的緣由)

  ![](https://i.imgur.com/rLruhs3.png)

* 所以為了跳過不可能有答案的區域，我們要知道 要怎麼構建所謂的 next[ ] 陣列 (或者你可以稱它為 部分匹配表(Partial Match Table))　［參 [海納的說法](https://www.zhihu.com/question/21923021/answer/281346746)］
   　　建構部分匹配表的過程可視為字串匹配的過程，圖片的說明請看 [海納的說法](https://www.zhihu.com/question/21923021/answer/281346746)。
可以想像，建構部分匹配表 其實是 **2 個字串在一一地對應**，他需要考慮 3 個狀況:
   　**1. 當 前綴 i = 後綴 j**，那麼 將 a[j] 匹配到 a[i] 的下一項
   　**2. 當 前綴第一項 不等於 後綴 j 時 時**，那麼 後綴往後移一位 (為了匹配阿)
   　**3. 當 前綴 不等於 後綴 j 時**，將前綴往前回溯  (試試看後綴 j 是否等於 next[前綴 i])
ˊ而當後綴超出邊界後，next[ ] 匹配表即製作完成   





:::

:::success
* 
* https://yeefun.github.io/kmp-algorithm-for-beginners/
* https://www.zhihu.com/question/21923021/answer/281346746
:::
&emsp;

# Day 3 離線演算法

## 1. 莫隊算法
### [Distinct Values Queries](https://cses.fi/problemset/task/1734)

```csharp=
#include <bits/stdc++.h>
#define ll long long
#define L second.first
#define R second.second
#define id first
using namespace std;

ll n, q, B, l , r;
ll seq[200001], ans_[200001], kind[200001];
pair<ll, pair<ll, ll>> queries[200001];

void init()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for (ll i = 0; i < n; i++) 
        cin >> seq[i];
    
    for (ll i = 0; i < q; i++) {
        cin >> queries[i].L >> queries[i].R;
        queries[i].L--;
        queries[i].R--;
        queries[i].id = i;
    }
}

void discrete()       // 離散化
{
    vector<ll> vec(seq, seq + n);
    sort(vec.begin(), vec.end());
    vec.assign(vec.begin(), unique(vec.begin(), vec.end()));
    for (ll i = 0; i < n; i++)
        seq[i] = lower_bound(vec.begin(), vec.end(), seq[i]) - vec.begin();
}

void Mos_algorithm()  // 莫隊算法
{
     B = n / max((int)sqrt(q), 1);

     sort(queries, queries + q, [&](const pair<ll, pair<ll, ll>>& i, const pair<ll, pair<ll, ll>>& j)
     {
        if (i.L / B == j.L / B)
            return i.R < j.R;
        else
            return i.L / B < j.L / B;
     });
}

void solve()
{
    ll l = 0, r = -1, ans = 0;
    for (ll qi = 0; qi < q; qi++)
    {
        while (queries[qi].R > r) {
            r++;
            if (++kind[seq[r]] == 1)
                ans++;
        }
        while (queries[qi].L < l) {
            l--;
            if (++kind[seq[l]] == 1)
                ans++;
        }
        while (queries[qi].L > l) {
            if (kind[seq[l]]-- == 1)
                ans--;
            l++;
        }
        while (queries[qi].R < r) {
            if (kind[seq[r]]-- == 1)
                ans--;
            r--;
        }

        ans_[queries[qi].id] = ans;
    }

    for (ll i = 0; i < q; i++)
        cout << ans_[i] << endl;
}

int main()
{
    init();
    discrete();
    Mos_algorithm();
    solve();
}
```
:::info
(知識點1) **莫隊算法**

* 莫隊算法是一種離線演算法。它會將區間讀起來，**整理成一定的順序**，再讓**爬行法**去走訪它
* 但究竟是怎樣的順序才能讓莫隊有著 **O( N * (Q)^(1/2))** 的複雜度呢?
　　其實莫隊的順序先 **按左界將 n 個區間 分成 B 塊**，再**讓每一塊由右界排序**。
  　　這樣的排序法 <span style="border-bottom:2px dashed yellow;">使**左界最多移動 O( B * Q )** < ps: B 為每一塊的長度>，右界最多移動 **O( N * N/B)** < N 為每 (次) 塊最多移動的距離、N/B 為塊數(移動次數) >  <span/>由算幾不等式， **當 B取 N / (Q)^(1/2) 時**， Ｏ 有佳複雜度值 N * (Q)^(1/2)。而通常此複雜度即足以 AC 了
    
* 詳細資訊可以參 [OI wiki 的教學](https://oi-wiki.org/misc/mo-algo/)
:::
:::success
* 此題除了考了 "莫隊算法"，也考了 "**離散化**"
* 為了算出區間內有幾種數字，我們需要一個容器來儲存各個數字種類的個數。
    　**如果使用 map 來做，bigO 會是 O( n * log(n) * (n)^ 1/2 )** ( 顯然這樣會吃 TLE )
    所以我們得 **事先做好離散化**，這樣才能保證 bigO 不僅維持不變，也能將 10^9 的數字範圍縮小。
* 題外話: 這題也可以用 BIT 做
:::
&emsp;
    
## 2. cdq 分治
### [三維偏序問題](https://zerojudge.tw/ShowProblem?problemid=c571)
```csharp=
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll arr[100001] = {0}, maxN = 0;
struct Fenwick
{
    ll query(ll r)          // 1 based
    {
        ll num = 0;
        while (r != 0) {
            num += arr[r];
            r -= r & (-r);
        }
        return num;
    }

    void update(ll val)
    {
        if (val < 0) {
            ll i = -val;
            while (i <= maxN) {
                arr[i] -= 1;
                i += i & (-i);
            }
        }
        else
        {
            ll i = val;
            while (i <= maxN) {
                arr[i] += 1;
                i += i & (-i);
            }
        }
    }
}BIT;

struct Point
{
    ll x, y, z, i;
};

ll n, ans[100001] = {0};
Point P[100001];

vector<Point> cdq(ll l, ll r, ll p);
bool comp(Point i, Point j) { return (j.x > i.x); }
bool comp2(ll i, Point j) { return (i < j.x); }
bool comp3(ll i, Point j) { return (i < j.y); }
int main()
{
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> P[i].x >> P[i].y >> P[i].z;
        P[i].i = i;
        maxN = max(maxN, P[i].z);
    }

    sort(P + 1, P + n + 1, comp);

    vector<Point> sorted;
    ll s = 0, t = 0;
    while (t <= n)
    {
        t = upper_bound(P + 1, P + n + 1, P[s].x, comp2) - P;
        sorted = cdq(s, t - 1, -1);
        s = t;
    }


    sorted = cdq(1, n, 1);

    for (ll i = 1; i <= n; i++)
        cout << ans[i] << endl;
}
------------------------------- cdq 重點在下面-------------------------------
    
vector<ll> record;
vector<Point> cdq(ll l, ll r, ll p)
{
    vector<Point> sorted;
    if (l == r) {
        sorted.push_back(P[r]);
        return sorted;
    }

    ll mid = (l + r) / 2, j = 0;
    vector<Point> vec1 = cdq(l, mid, p), vec2 = cdq(mid + 1, r, p);

    for (ll i = 0; i < vec1.size(); i++) {
        while (j < vec2.size() && vec2[j].y > vec1[i].y) {
            sorted.push_back(vec2[j]);   // 如果是 x 大 、y 也大的 vec2，
            BIT.update(vec2[j].z);       // 就在 BIT 中儲存 z 的位置 
            record.push_back(vec2[j].z); 
            j++;
        }                             // 如果是 x 小但 y 大的 vec1，
                                      // 就將這之前 y 大於我的數， 
        sorted.push_back(vec1[i]);    // 數出有幾個 z 也大於我
        ans[vec1[i].i] += (BIT.query(maxN) - BIT.query(vec1[i].z)) * p;
    }

    while (j < vec2.size()) {
        sorted.push_back(vec2[j]);
        j++;
    }

    for (ll opt : record)    // 如果每次遞迴就要重新宣告 BIT， 時間複雜度會不好
        BIT.update(-opt);    // 因此我們會將過程中 BIT 的操作先紀錄下來，
                             // 直到最後再撤銷 (update(-opt))
    record.clear();

    return sorted;
}
```
:::info
(知識點1) **cdq 分治**

* cdq 的核心想法始於 **三維偏序**，也可以說，會了 三維偏序即會了 cdq。
而 cdq 的思路 由 **處理象限** 開始。
                           
* 當我做 三維偏序 (cdq) 時，我會先思考要==怎麼處理 x 象限== (通常用**sort** 排序)，再來想==要怎麼處理 y 象限== (通常用 **分治**的插入排序)，最後再想 ==要怎麼處理 z 象限== ( 此題可以用 **BIT**)。<u>當我每一個象限 (狀況) 都處理完畢後，cdq 分治即 思考完成了 </u>
* 接下來談實作的部分，cdq 分治 其實就是 **merge sort 的應用**，還記得 merge sort 怎麼寫八? 設立邊界 case，再將 兩邊的 vec 依大小做合併。有了這個基礎概念，再 "將想要處理的問題加入"， 就可以解決 cdq 分治了!                      
:::
:::success
* 此題的複雜度是 **merge sort: O(n * log(n)) + BIT : O(log(C ))** = O(n* log(n) * log( C))，
    而如果有<u>先將所有維度先離散化</u>，複雜度會降為 O(n * (log(n) ^ 2))
:::

&emsp;                           

# Day5 PCCA Winter Camp Contest 2023
## [Problem E. Exterior](https://codeforces.com/gym/425267)
### <法一> 將 portal 連向虛點，即能用 Dijkstra

```csharp=
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#define ll long long
#define pll pair<ll, ll>
#define oo 100000000
using namespace std;

ll n, m, a, u, v, c, dist_;
vector<pll> graph[100001];
priority_queue<pll> pq;
ll dist[100001];
bool visit[100001] = {false};

int main()
{
    cin >> n >> m;

    for (ll i = 1; i <= n; i++) {
        cin >> a;
        graph[i].push_back({ -a, 0 });
        graph[0].push_back({ -a ,i });
    }

    for (ll i = 0; i < m; i++) {
        cin >> u >> v >> c;
        graph[u].push_back({ -c ,v });
        graph[v].push_back({ -c ,u });
    }

    for (ll i = 0; i <= n; i++) {
        if (i != 1) {
            dist[i] = -oo;
            pq.push({ -oo, i });
        }
    }
    dist[1] = 0;
    pq.push({ 0, 1 });

    while (!pq.empty())
    {
        if (!pq.empty() && visit[pq.top().second]) {
            pq.pop();
            continue;
        }

        tie(dist_, u) = pq.top();
        if (dist[u] != -oo)
            visit[u] = true;

        for (pll path : graph[u]) {
            tie(c, v) = path;
            if (!visit[v] && dist_ + c > dist[v]) {
                dist[v] = dist_ + c;
                pq.push({ dist[v], v });
            }
        }
    }

    cout << -dist[n];

}
```
:::success
* 真的沒想到可以將 portal 連向虛點 !! 像這種**建立變數，輔助線，虛點、假力 的想像術**，難想到啊
:::