# PCCU 營隊筆記
 
---
# 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;
}
```
 
## 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 要不要走，這個概念可以用以下圖表來呈現:
由 圖中可以看到當我們將數字轉為二進位表示時，我們可以造出 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 )
:::
---
 
# 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 了，卻很不幸地在最後 "因為不相等而重新來過"。
當這種情況發生時，模式串會"**不長進地**" 往下掉一位 再重新計算。為甚麼我會說他不長進呢? 因為他明明**有上一回合的資訊**，卻放著不用、硬是呆呆地重來計算，當然不長進!
* 於是乎為了利用上一回合的資訊 (及減少無謂的計算)，我們有了個想法 --- 如果每次跳過不可能有答案的區域，是否就能減少計算?
( 可以想一下**為甚麼以下 2 個模式串會被跳過** (被打 xx 了)，這隱含著做部分匹配表的緣由)
* 所以為了跳過不可能有答案的區域，我們要知道 要怎麼構建所謂的 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
:::
 
# 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 做
:::
 
## 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))
:::
 
# 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 連向虛點 !! 像這種**建立變數，輔助線，虛點、假力 的想像術**，難想到啊
:::
Sign in with Wallet
Connect another wallet