總有一天會用到的筆記

【題解】CSES 1680. Longest Flight Route

發表於 2021-11-16

本篇尚在施工中...

【模板】Treap

發表於 2021-11-16 分類於競程

本篇尚在施工中...

Treap 可以做到很多酷酷的序列操作。本篇主要討論 Split/Merge Treap。

基礎概念

key 決定左右順序，pri 值決定上下順序

Treap 是一棵二元樹，每個節點都包含 key 和 pri 值，並且符合性質 1. 左子樹的 key 都小於自己，右子樹的 key 都大於自己；2. 子節點的 pri 都比父節點大

只要透過 key 和 pri 便能唯一決定這棵樹的長相

以透過 split(u,k) 和 merge(a,b) 操作樹

split(u,k) 將一棵 Treap 分成兩棵，其中一棵鍵值皆小於 k，另一棵鍵值皆大於 k merge(a,b) 將兩棵 Treap 合併，其中一棵鍵值皆小於 k，另一棵鍵值皆大於 k（和 split 為反操作）

只要好好遵守函數定義，我們可以在不破壞 Treap 性質的條件下對他動手動腳：

想要插入，就把一顆 treap 切開後，把東西塞進去，再 merge 回去想要刪除，就把一顆 treap 切兩刀，丟掉中間，再 merge 回去

key 和 pri 塞入不同數字，樹的意義會不同。

key 和 pri 可以自己賦予意義，例如：

key = index, pri = value：得到一顆笛卡爾樹。 key = value, pri = random：可以支援動態排序 key = index, pri = random, data = value：拿來維護序列（data 為無關乎樹的長相，節點內存的資料）

採用隨機的 pri 值，防止退化

不管是 split、merge、在樹上查找，複雜度都與深度相關。

Treap 的精髓在於，採用隨機的 pri 值，使整顆樹的期望深度為 $logn$，複雜度更好。

以維護 size 代替 key = index

拿 Treap 來維護序列是很常見的用法，但想像一下插入節點的過程。我們需要把插入位置前、後的 key 值都做改變，顯得非常麻煩。

把 key 丟棄不用，反正只要再 split 和 merge 的時候，保證兩棵 treap 是不相交的連續區間，並且知道大小關係就好了。

但把 key=index 丟棄之後，要怎麼知道這個節點是第幾個？維護每個節點的 size，這樣在搜下去的過程中，就能算出這個節點的 index

如下圖，節點 3 的 index 為 6：

實作

判斷當前節點是不是答案、要不要被包括進分割

動態排序

get_rank(x)，有幾個數字小於 x，每次插入、刪除自己找出目標位置
insert(x)
erase(x)

區間加值

區間反轉

【模板】快速傅立葉變換

發表於 2021-10-25 更新於 2021-12-10 分類於競程

樸素的多項式乘法，必須在 $O(n^2)$ 完成。

我們可以透過 FFT 的協助，在 $O(nlogn)$ 時間內完成多項式乘法。

點值表達式

可以帶入至少 $n$ 個點來唯一表示 $n-1$ 次多項式。

所以，$n > deg\ f(x)$，$f(x)$ 能以點值表達式表示為

\[(x_0,f(x_0)), (x_1,f(x_1)), \dots, (x_{n-1},f(x_{n-1}))\]

兩個點值表達式的乘法可以在 $O(n)$ 達成，$(fg)(x)$ 可以被表示為：

\[(x_0,f(x_0)g(x_0)), (x_1,f(x_1)g(x_1)), \dots, (x_{n-1},f(x_{n-1})g(x_{n-1}))\]

記得取 $n > deg\ (fg)(x)$

因此對於多項式乘法，我們有了計畫：

係數表達式 $\rightarrow$ 點值表達式 $\rightarrow$ $O(n)$ 相乘 $\rightarrow$ 點值表達式 $\rightarrow$ 係數表達式

我們的瓶頸將會在，如何快速的做到係數表達式轉換點值表達式

FFT

定義一個函數 $FFT$，傳入 $X_0, X_1, \dots, X_{n-1}$ 和 $n$ 個係數 $P_0, P_1, \dots, P_{n-1}$，可以計算出帶入 $X$ 的結果是多少。

\[ FFT(X,P) = \begin{bmatrix} X_0^0 & X_0^1 & \dots & X_0^{n-1}\\ X_1^0 & X_1^1 & \dots & X_1^{n-1}\\ \vdots & \vdots & \ddots & \vdots \\ X_{n-1}^0 & X_{n-1}^{1} & \dots & X_{n-1}^{n-1} \end{bmatrix} \begin{bmatrix} P_0\\ P_1\\ \vdots\\ P_{n-1}\\ \end{bmatrix} = \begin{bmatrix} f(X_0)\\ f(X_1)\\ \vdots\\ f(X_{n-1})\\ \end{bmatrix}\]

為了減少計算量，我們可以利用偶函數的性質：$f(x) = f(-x)$，只要帶入一個數字就能得到兩份結果：

\[ \begin{aligned} f(x) & = p_0x^0 + p_1x^1 + \dots + p_{n-1}x^{n-1}\\\\ & = (p_0x^0 + p_2x^2 + \dots + p_{n-2}^{n-2}) + x(p_1x^1 + p_3x^2 + \dots + p_{n-1}^{n-2}) \end{aligned}\]

為了更方便觀察出遞迴的性質，以及 $f(x)$ 和 $f(-x)$ 的關係，可以這樣表示：

\[ \begin{aligned} &f(x) = f_e(x^2) + xf_o(x^2)\\ &f(-x) = f_e(x) -xf_o(x^2)\\ &f_e(x) = p_0x^0 + p_2x^2 + \dots + p_{n-2}x^{\frac n 2 -1}\\ &f_o(x) = p_1x^0 + p_3x^2 + \dots + p_{n-1}x^{\frac n 2 -1}\\ \end{aligned} \]

現在，只要算出 $f(x)$ 就能順便得到 $f(-x)$。把後半的 $X$ 皆對應到前半的 $X$，使他們互為相反數：

\[ X_i = X_{i+\frac n 2}, i<\frac n 2 \]

這樣就有了 $FFT$ 函數的轉移，大概長這樣：

\[ FFT(X,P) = merge( FFT(X_{half},P_{even}),\ FFT(X_{half},P_{odd})) \]

\[ X_{half} = [X_0, X_1, \dots, X_{\frac n 2-1}] \\ P_{even} = [P_0, P_2, \dots, P_{n-2}] \\ P_{odd} = [P_1, P_3, \dots, P_{n-1}] \\ \]

$merge$ 的地方，就是第 $i$ 項相加得到 $f(X_i)$，相減得到 $f(X_{i+\frac n 2})$

接著需要處理，$X$ 裡面究竟該放什麼，才能順利的遞迴下去。考慮：

\[ X = [a_0, a_1, \dots, a_{n-1}] \]

遞迴下去會變成：

\[ [a_0^2, a_1^2, \dots, a_{\frac n 2 -1}^2] \]

我們需要在遞迴的每一層都保證後半部是前半部的相反數，也就是 $X_i = X_{i+\frac n 2}, i<\frac n 2$。

只考慮實數是不可能的，因為下一層是上一層的平方，不會是相反數。

單位複根

定義 $\omega_n^i$ 為 $x^n=1$ 下的其中一個解，這樣的解有 $n$ 個，把單位圓等分，且有以下性質我們會用到的性質：

\[ \omega_n^i = \omega_n^{i+\frac n 2}\\ (\omega_n^i)^2 = \omega_{\frac n 2}^i \]

這兩個性質用n次單位根等分單位圓、複數相乘幅角相加可以說明

直接取 $X_i = \omega_n^i$，單位根的性質恰好符合我們的要求：保持後半部是前半部的相反數

遞迴下去之後，$X = [\omega_{\frac n 2}^0, \omega_{\frac n 2}^1, \dots, \omega_{\frac n 2}^{\frac n 2 -1}]$，依舊保證了這件事。

Inverse FFT

前面有提到 FFT 可以看成矩陣相乘的過程，那個 $n \times n$ 的矩陣我們叫他 $DFT$ 矩陣。

從點值找出係數的過程，就是左右乘上 $DFT^{-1}$，而 $DFT^{-1}$ 長這樣：

\[ \begin{bmatrix} \omega_0^0 & \omega_0^{-1} & \dots & \omega_0^{-(n-1)}\\ \omega_1^0 & \omega_1^{-1} & \dots & \omega_1^{-(n-1)}\\ \vdots & \vdots & \ddots & \vdots\\ \omega_{n-1}^0 & \omega_{n-1}^{-1} & \dots & \omega_{n-1}^{-(n-1)}\\ \end{bmatrix} \]

就是每個元素都倒數，原因我不是很清楚。

實作

\[ \omega_n^k = cos \frac{2 \pi k}{n}i + sin \frac{2 \pi k}{n}i \]

這很容易在複數平面上看端倪。

實作時就用這個公式及 C++ 內建的 Complex 處理即可。

【題解】TOJ 639. Hello, Weird Music Sheet!

發表於 2021-09-28 更新於 2021-11-16

題意

給定 $n$，求有多少種 $a$ 使 $a_1 \le a_2 \ge a_3 \le a_4 ...a_n$ 且 $0 \le a_i \le 11$。

$n \le 10^{18}$

觀察

可以考慮 DP，設 $dp[i][j]$ 為當 $a_{i+1} = j$，$a_1 \ldots a_i$ 有多少種可能性
轉移：

\[ dp_{i,j} = \begin{cases} \begin{aligned} &dp_{i-1,0} + \ldots + dp_{i-1,j} & \text{if } j \equiv 1 \mod{2}\\ &dp_{i-1,j} + \ldots + dp_{i-1,11} & \text{else} \end{aligned} \end{cases} \]

$n$ 很大想到可以用矩陣快速冪
奇數->偶數和偶數->奇數的轉移式不同

作法

把 $dp_{i,0}$ 到 $dp_{i,11}$ 合起來，再考慮線性遞迴： \[ D_i = \begin{bmatrix} dp_{i,0} & dp_{i,1} & dp_{i,2} & \ldots & dp_{i,11} \end{bmatrix} \]

可以得到偶數項到奇數項的轉移矩陣為：

\[ A_1 = \begin{bmatrix} 1 & 1 & 1 & \ldots & 1\\ 0 & 1 & 1 & \ldots & 1\\ 0 & 0 & 1 & \ldots & 1\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \ldots & 1 \end{bmatrix} \]

奇數項到偶數項的轉移矩陣：

\[ A_2 = \begin{bmatrix} 1 & 0 & 0 & \ldots & 0\\ 1 & 1 & 0 & \ldots & 0\\ 1 & 1 & 1 & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & 1 & \ldots & 1 \end{bmatrix} \]

則當 $n$ 為偶數： \[ \begin{aligned} D_n & = D_0 \times A_1 \times A_2 \times \ldots \times A_2\\ & = D_0 \times (A_1 \times A_2)^{\frac{n}{2}} \end{aligned} \]

否則： \[ \begin{aligned} D_n & = D_0 \times A_1 \times A_2 \times \ldots \times A_1 \\ & = D_0 \times (A_1 \times A_2)^{\lfloor \frac{n}{2} \rfloor} \times A_1 \end{aligned} \]

這樣我們就能矩陣快速冪了。

這邊附上矩陣快速冪的模板：

struct mat{
    vector<vector<int>> v;
    mat(){
        v.resize(N,vector<int>(N));
    }
    mat operator * (mat y){
        mat res;
        for (int i=0; i<N; i++){
            for (int j=0; j<N; j++){
                for (int k=0; k<N; k++){
                    res.v[i][j] += v[i][k]*y.v[k][j];
                }
            }
        }
        return res;
    }
} I;

mat qpow (mat x, int y){
    mat res = I;
    for (; y; y>>=1,x=x*x){
        if (y&1){
            res = res*x;
        }
    }
    return res;
}

AC Code

const int N = 12, M = 1e9+7;

struct mat{
    vector<vector<int>> v;
    mat(){
        v.resize(N,vector<int>(N));
    }
    mat operator * (mat y){
        mat res;
        for (int i=0; i<N; i++){
            for (int j=0; j<N; j++){
                for (int k=0; k<N; k++){
                    res.v[i][j] += v[i][k]*y.v[k][j];
                    res.v[i][j] %= M;
                }
            }
        }
        return res;
    }
} A1, A2, D0, I;

mat qpow (mat x, int y){
    mat res = I;
    for (; y; y>>=1,x=x*x){
        if (y&1){
            res = res*x;
        }
    }
    return res;
}

int n;

signed main(){
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            A1.v[i][j] = (j>=i);
            A2.v[i][j] = (j<=i);
        }
    }
    for (int i=0; i<N; i++){
        I.v[i][i] = 1;
        D0.v[0][i] = 1;
    }
    cin >> n;
    mat trans = qpow(A1*A2,n/2);
    if (n&1) D0 = D0*trans*A1, cout << D0.v[0][11] << '\n';
    else D0 = D0*trans, cout << D0.v[0][0] << '\n';
}

【題解】TOJ 637. 本田小狼

發表於 2021-09-28 更新於 2021-11-16 分類於競程

題意

給一顆有根樹。多次詢問 $p$、$k$，求 $p$ 的子樹往下最多走 $k$ 步可以到達幾個節點。

觀察

若從 $u$ 往下走 $k$ 步可以到達 $v$，等價於 $d[v] \le d[u]+k$。題目相當於詢問 $u$ 子樹內有多少子節點深度 $\le d[u]+k$。

作法

區間查詢 $x$ 數量

給你一個序列 $a$，多筆查詢 $\le k$ 的數字有多少。我們可以對值域開一個序列上的資料結構 $cnt$，當出現值為 $x$ 的元素就 $cnt[x]++$，查詢時答案就是 $cnt[1]+...+cnt[k]$。

進階一點，給你一個序列 $a$，多筆區間查詢 $\le k$ 的數字有多少。只要我們能只把 $a[l], a[l+1], ..., a[r]$ 放進資料結構，就能用同樣的方式查詢。

如果序列只有一種值，那等於只要 $r$ 時有多少個減 $l$ 時有多少個就可以得出答案。推廣到整個序列的很多種值，我們只要每個資料結構的每個位置相減就行：把 $a[i]$ 放進陣列後，我們紀錄現在的 $cnt$ 為 $cnt_i$，當只要 $a[l], a[l+1], ..., a[r]$ 放進陣列的結果，就把 $cnt_r$ 跟 $cnt_l$ 的每個元素相減得到 $cnt_p$ 。

我們的 $cnt$ 以持久化線段樹實作，支援單點修改、查詢版本 $i$ 下的區間和。

持久化線段樹

因為每次修改只會更動 $logn$ 個值，我們只要紀錄被更改的節點就好。

對於每次修改我們想像開一顆新的線段樹作為最新的版本，但是子樹若長得完全ㄧ樣就指回去上個版本。

實作要注意：

修改時必須回傳新的節點
若子樹一樣必須指回去上個版本
從外面呼叫修改時，要拿一個陣列儲存新的線段樹的根
可以不用事先 build，全部指到 $0$

int root[N];
struct Seg{
    int tr[N<<5], lc[N<<5], rc[N<<5], ptr;
    
    int modify (int u, int i, int x, int l=1, int r=n){
        int rt = ++ptr;
        lc[rt] = lc[u], rc[rt] = rc[u], tr[rt] = tr[u];
        if (l == r){
            tr[rt] += x;
        }
        else{
            int m = (l+r)>>1;
            if (i <= m) lc[rt] = modify(lc[u],i,x,l,m);
            if (m < i)  rc[rt] = modify(rc[u],i,x,m+1,r);
            tr[rt] = tr[lc[rt]] + tr[rc[rt]];
        }
        return rt;
    
    }
    int query (int u, int ql, int qr, int l=1, int r=n){
        if (ql<=l && r<=qr){
            return tr[u];
        }
        int m = (l+r)>>1, ans = 0;
        if (ql<=m) ans += query(lc[u],ql,qr,l,m);
        if (m<qr) ans += query(rc[u],ql,qr,m+1,r);
        return ans;
    }
} st;

樹壓平

題目都是查詢子樹，因此只要保證子樹在連續區間內，就能套用上面的方法。

dfs 進去時紀錄 $tin[u] = ++time$，出來時紀錄 $tout[u] = ++time$。因為一定子樹走完才會出來，因此子樹一定被 $tin[u]$ 和 $tout[u]$ 夾住。

有個優化的方式，出來時不佔用另一個 $time$，就讓多個 $tout$ 指在同一個地方，如此序列大小減半且答案不需要除以 $2$。

int dseq[N], tin[N], tout[N], tim;
void dfs (int u, int fa, int d){
    tin[u] = ++tim;
    dseq[tin[u]] = d;
    for (auto v: G[u]){
        if (v == fa) continue;
        dfs(v,u,d+1);
    }
    tout[u] = tim;
}

AC Code

const int N = 1e6+10;

int n, q;
vector<int> G[N];

int dseq[N], tin[N], tout[N], tim;
void dfs (int u, int fa, int d){
    tin[u] = ++tim;
    dseq[tin[u]] = d;
    for (auto v: G[u]){
        if (v == fa) continue;
        dfs(v,u,d+1);
    }
    tout[u] = tim;
}

int root[N];
struct Seg{
    int tr[N<<5], lc[N<<5], rc[N<<5], ptr;
    int modify (int u, int i, int x, int l=1, int r=n){
        int rt = ++ptr;
        lc[rt] = lc[u], rc[rt] = rc[u], tr[rt] = tr[u];
        if (l == r){
            tr[rt] += x;
        }
        else{
            int m = (l+r)>>1;
            if (i <= m) lc[rt] = modify(lc[u],i,x,l,m);
            if (m < i)  rc[rt] = modify(rc[u],i,x,m+1,r);
            tr[rt] = tr[lc[rt]] + tr[rc[rt]];
        }
        return rt;
    
    }
    int query (int u, int ql, int qr, int l=1, int r=n){
        if (ql<=l && r<=qr){
            return tr[u];
        }
        int m = (l+r)>>1, ans = 0;
        if (ql<=m) ans += query(lc[u],ql,qr,l,m);
        if (m<qr) ans += query(rc[u],ql,qr,m+1,r);
        return ans;
    }
} st;

signed main(){
    minamisan
    cin >> n;
    rep(i,2,n){
        int u, v;
        cin >> u >> v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    dfs(1,1,1);
    
    rep(i,1,n){
        root[i] = st.modify(root[i-1],dseq[i],1);
    }
    
    cin >> q;
    rep(i,1,q){
        int p, k;
        cin >> p >> k;
        cout << (st.query(root[tout[p]],1,k+dseq[tin[p]])-st.query(root[tin[p]-1],1,k+dseq[tin[p]])) << '\n';
    }
}

【題解】TOJ 638. 遞回呀遞回

發表於 2021-09-27 更新於 2021-11-16 分類於競程

題意

$a, b, c, r_0, r_1, n, p$ 和遞迴關係式 $r_{i+2} = a \cdot r_{i+1} \cdot r_i + b \cdot r_{i+1} + c \cdot r_i$，求 $r_n \mod p$

$n \le 10^{18}$
$p \le 10^4$

觀察

因為有 $r_{i+1} \cdot r_i$，不能用矩陣快速冪
只會用到前兩項
$p \le 10^4$，因此前兩項的可能性不超過 $10^8$ 種

作法

當只要出現兩項 ${f[i-1],f[i]}$ 曾經出現過，就代表接下來會循環： $A, B, C, ..., X, ..., X, ..., X...$

我們紀錄第一次循環出現的位置和循環節長度，若 $n$ 在循環出現前可以直接回答，否則計算出 $n$ 在循環節中的哪個位置再回答。

AC Code

const int N = 5e7;

int a, b, c, r0, r1, n, p;
int f[N];
map<pii,int> mp; //{{f[i-1], f[i]}, i}

signed main(){
    cin >> a >> b >> c >> f[0] >> f[1] >> n >> p;
    a%=p, b%=p, c%=p, f[0]%=p, f[1]%=p;
    mp[{f[0],f[1]}] = 1;

    int op, len;
    rep(i,2,N){
        f[i] = ((a*f[i-1]*f[i-2]%p + b*f[i-1]%p + c*f[i-2]%p)%p+p)%p;
        if (mp[{f[i-1],f[i]}] != 0){
            op = mp[{f[i-1],f[i]}];
            len = i - op;
            break;
        }
        mp[{f[i-1],f[i]}] = i;
    }
    if (n <= op+len) cout << f[n] << '\n';
    else cout << f[(n-op)%len+op] << '\n';
}

【模板】KMP

發表於 2021-09-25 更新於 2021-12-06 分類於競程

KMP 用在字串匹配，可以在字串 $S$ 中找到哪些地方出現過字串 $P$。

核心思想是優化樸素的字串匹配過程。匹配可以視作，每個位移過後的 $P$，有哪些與對應的 $S$ 子字串相等：

S  AABAABAAC
P1 AABAAc
P2  Aabaac
P3   aabaac
P4 	  AABAAC
每個都匹配到失敗為止，並且從匹配失敗之後用小寫表示

在匹配過程中，想辦法跳過會更早失敗的 $P$。

在匹配過程中，有時會失敗在某個地方，如在第 1 次匹配中 $S[4] \ne P[4]$。第 2和第 3 次匹配，會在更早的地方失敗。我們想直接跳過 2、3 次匹配。要找到下一個至少不會在 $i<4$ 就匹配失敗的。可以發現，這相當於把 $P$ 字串位移直到其次長前綴 = 匹配失敗前的後綴（最長就根本沒位移）：

1 2	P1 AAB[AA]c P4 [AA]BAAC

訂定函數 $f(i)$，代表 $P[0,i)$ 次長共同前後綴長度（最長但不包括 $P[0,i)$ 本身）

上面的想法，相當於以 $i$ $j$ 兩個指針來匹配 $S$ 和 $P$，一但失敗就使 $j$ 回到最次長前綴。定義 $f(i)$ 可以方便地做到這件事。

轉移：$f(i+1) = f(j)+1,\ P[j] = P[i]$

我們來計算 $f(i)$。只要 $P[f(i)] = P[i]$，則 $f(i+1) = f(i)+1$ 那如果不相等呢？也還有機會：

因為 $P[0, f(i)) = P[i-f(i),i)$，所以 $P[0,f(f(i))) = P[i-f(f(i),i)$。此時只要從 $f(i)$ 退到 $f(f(i))$，再試試看就好了。

基底：$f(0) = -1,\ f(1) = 0$

顯然，$f(1) = 0$。那 $f(0)$ 呢？在匹配過程中會出現 $f(0)$，即是當 $S[i]$ 和 $P[0]$ 匹配，而且還失敗的時候。這時就直接放棄這個 $S[i]$，從 $S[i+1]$ 和 $P[0]$ 開始重新匹配了。我們令 $f(0) = -1$，方便我們知道 $S[i]$ 和 $P[0]$ 匹配失敗，該直接跳過了。實作時會體現 $-1$ 的方便性。

以下是 $f$ 建表的實作：

f[0]=-1, f[1]=0;
for (int i=1,j; i<p.size(); i++)
{
    for (j=f[i]; j>=0 && p[j]!=p[i]; j=f[j]);
    f[i+1] = j+1;
}

以 $i$ 遍歷 $S$，$j$ 遍歷 $P$，對於每個 $i$ 找到第一個與其匹配的 $j$

匹配 $i$ 與 $j$ 一但成功，就能幫下個 $i$ 找匹配的 $j$。否則，就找到下一個可能與 $i$ 匹配的 $P$。另外，當 $i$ 與 $j=0$ 匹配失敗，就 $i++,j=0$。

出現完全成功配對的條件，是過程中發生，$i=|S|-1$ 和 $j=|P|-1$ 匹配成功。下層迴圈中 $j = |P|$，必須使 $j = f[j]$。實作用到了一個細節是，p[p.size()] 會拿到 p.end()，所以不用擔心 RE。ㄦ

for (int i=0,j=0; i<s.size(); i++,j++)
{
    while (j>=0 && s[i]!=p[j]) j = f[j];
    if (j == p.size()-1) ans++;
}

【模板】連通分量

發表於 2021-09-25 更新於 2022-06-14 分類於競程

名詞解釋

連通分量：數量最多、擴展範圍最大
割點：把這個點拔掉會增加連通塊數量
橋：把這個邊拔掉會增加連通塊數量
無向連通分量
- 橋連通分量（邊雙連通分量）：一個連通分量內，拔掉任一邊連通塊數量不會增加
- 點雙連通分量：一個連通分量內，拔掉任一點連通塊數量不會增加
有向圖連通分量
- 強連通分量：一個連通分量內，a 能到 b、b 能到 a

DFS Tree

把一張圖 DFS，邊可以分成四種：

Tree Edge：DFS 過程中經過的邊。DFS 時，走向沒走過的臨點的鄰邊都是 Tree Edge。
Back Edge：通向祖先的鄰邊。
Forward Edge：不再 DFS Tree 上，通向子樹的鄰邊。
Cross Edge：通向不存在父子關係的點的鄰邊。

在 DFS 時，遇到走訪過的邊就是下面三種之一。並且無向圖只存在 Tree Edge 和 Back Edge（Forward Edge 因為無向等同於 Back Edge；u 若存在 Cross Edge 連到 v，那在 v 時就應改把這條邊當成 Tree Edge）。所以討論連通的時候，只需要討論子孫和祖先的關係。

Tarjan's BCC

割點

在 DFS Tree 上當一個點被拔掉，子孫還想要跟祖先點互通有無，那就只能透過 Back Edge 了。如果這個子樹中有一條 Back Edge 可以回到任一個祖先，那點被拔掉就不會影響該子樹根祖先互通。反之若其中一個子樹不存在 Back Edge 可以連回祖先，那該點就是割點。

low 函數

我們可以記錄該點的子孫通過 Back Edge 最上面可以連到哪裡，這樣祖先們都能用它該點是否可以走到自己上面。我們稱它為 $low(u)$。當走 Tree Edge 到子節點，可以直接拿他的 $low$；或是走 Back Edge 到祖先，則拿他的深度。

特判根

沒有人可以透過 Back Edge 走到根上面。根是割點，若且唯若根有兩個以上的子節點。

Tarjan 求割點實作

維護 dep、low
檢查該點是否為割點，特判根。

vector<int> G[N];
int isap[N], low[N], dep[N];

void dfs (int u, int p){
    int child = 0;
    low[u] = dep[u] = low[p]++;
    for (auto v: G[u]){
        if (v == p) continue;
        if (dep[v]){
            low[u] = min(low[u], dep[v]);
        }
        else{
            dfs(v,u);
            child++;
            low[u] = min(low[u], low[v]);
            if (low[v] >= dep[u]){
                isap[u] = 1;
            }
        }
    }
    if (u==p && child<=1) isap[u] = 0;
}

點雙連通分量

維護一個 stack，我後面都是子孫並且跟我是同一個 BCC。如果我是這個 BCC 裏最淺的點，就把我以後的東西都 pop 出來，作為我 BCC 裡面的點。如果該點是割點，記得放回去（最淺的那個點一定是割點），因為割點還會屬於其他 BCC。

當沒有兒子的時候需要特判。

vector<int> G[N];

int low[N], dep[N], n, m, bcnt;
vector<int> st, memb[N];
void dfs (int u, int p){
    if (u == p && G[u].size()<1){
        memb[bcnt++].pb(u);
        return;
    }
    low[u] = dep[u] = dep[p]+1;
    st.pb(u);
    for (auto v: G[u]){
        if (v == p) continue;
        if (dep[v]){
            low[u] = min(low[u], dep[v]);
        }
        else{
            dfs(v,u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dep[u]){
                bcnt++;
                while(1){
                    memb[bcnt].pb(st.back());
                    if (st.back() == u) break;
                    st.pop_back();
                }
            }
        }
    }
}

橋

當一條走往子樹的邊被拔掉，子樹還想跟自己互通，就要有一條 Back Edge 連到自己或祖先。

實作

維護 dep、low
確認連向子樹的邊是不是橋（子樹有沒有任一個節點有 Back Edge 連回自己或祖先）
子節點只要不走過來的邊就行

vector<int> G[N];
struct Edge {int u, v;};
vector<Edge> edges;

void add_edge (int u, int v)
{
	G[u].pb(edges.size());
	edges.pb({u,v});
	G[v].pb(edges.size());
	edges.pb({v,u});
}

int d[N], l[N], timestamp, bridge_cnt;
void tarjan (int u, int from)
{
	d[u] = l[u] = ++timestamp;
	for (auto e: G[u])
	{
		int v = edges[e].v;
		if (!d[v])
		{
			tarjan(v,e^1);
			l[u] = min(l[u], l[v]);	
			if (l[v] > d[u])
			{
				bridge_cnt++;
			}
		}
		else if (e!=from)
		{
			l[u] = min(l[u], d[v]);
		}
	}
}

橋雙連通

Kosaraju

Hexo + Github Pages 架站筆記

發表於 2021-09-21 更新於 2022-05-21 分類於 Misc

Hexo

想寫日記和技術筆記，但我巴哈的身分證字號後四碼忘了，只好自己架部落格。作為第一篇文章，來記錄這兩天晚上的折騰過程。

Hexo 初識

裝他（我自己沒裝 node.js）：

1 2	brew install node npm install -g hexo-cli

建立 hexo 專案：

1	$ hexo init [Directory]

或是把當前資料夾當成目錄：

1	$ hexo init

Hexo 會射一坨檔案進去，（常用）目錄結構列舉如下：

scaffolds：放模板
source：放 post（文章）和 page（如 about、tag）
themes：主題直接 clone 到裡面
config.yml：站點配置文件

注意，主題配置文件也叫 config.yml，別搞混了。

新增第一則 post

1	$ hexo new 'owo'

接著會新增 source/_posts/owo.md。刪除 post 直接刪該檔案即可。

1 2	$ hexo cl $ hexo g

前一個好像是清除暫存檔。後者把 hexo 檔案們編譯成靜態網站檔案。

接著，預覽你的網站。他會吐位址給你：

1	$ hexo server

Github Pages

首先建立一個名為 username.github.io 的公開 repo。

接著在 hexo 專案下安裝 deploy 套件：

1	$ npm install --save hexo-deployer-git

打開站點配置文件，修改 deploy 和 url 部分：

deploy:
  type: git
  repo: https://github.com/username/username.github.io.git
  branch: master

1	url: you_url.com

然後你就可以編譯並部署：

1 2	$ hexo cl $ hexo g -d #hexo generate && hexo deploy

Hexo 主題：Next

直接把 Next 主題 clone 到 themes 下：

1	$ git clone https://github.com/theme-next/hexo-theme-next themes/next

修改站點配置文件裡的 theme（預設為 landscape）:

1	theme: next

Next 有四大主題：

# Schemes
scheme: Muse
#scheme: Mist
#scheme: Pisces
#scheme: Gemini

標籤和分類

產生 tags 頁面和 categories 頁面：

1 2	$ hexo new page tags $ hexo new page categories

修改主題配置文件中的 menu

1
2
3

menu:
  tags: /tags/ || fa fa-tags
  categories: /categories/ || fa fa-th

其他頁面如法炮製即可。

在每篇貼文的開始可以指定 tags 和 categories：

---
title: Hexo + Github Pages 架站筆記
date: 2021-09-21 22:48:16
tags: 'Hexo'
catogories: '技術筆記'
---

tags 可以有好幾個，categories 只能有一個。

語言

修改站點配置文件中的 languages 成 zh-TW。

在主題資料夾下的 languages 資料夾可以找對應語言的翻譯對照。部分文件如下：

menu:
  home: 首頁
  archives: 歸檔
  categories: 分類
  tags: 標籤
  about: 關於
  search: 搜尋
  schedule: 時間表
  sitemap: 網站地圖
  commonweal: 公益 404

頭像

把頭像放在主題資料夾下的 source/images，然後更改主題配置文件（僅支援 gif）：

avatar:
  # Replace the default image and set the url here.
  url: /images/avatar.gif
  # If true, the avatar will be dispalyed in circle.
  rounded: true
  # If true, the avatar will be rotated with the cursor.
  rotated: false

參考資料

https://ithelp.ithome.com.tw/users/20119486/ironman/2944?page=1
https://zhuanlan.zhihu.com/p/30836436
https://theme-next.iissnan.com/theme-settings.html#use-bg-animation
https://blog.akizukineko.tw/hexo-next-themes-backgroudpic/

基礎概念

實作

動態排序

區間加值

區間反轉

點值表達式

FFT

單位複根

Inverse FFT

實作

題意

觀察

作法

AC Code

題意

觀察

作法

區間查詢 \(x\) 數量

持久化線段樹

樹壓平

AC Code

題意

觀察

作法

AC Code

名詞解釋

DFS Tree

Tarjan's BCC

割點

Tarjan 求割點實作

點雙連通分量

橋

實作

橋雙連通

Kosaraju

Hexo

Hexo 初識

新增第一則 post

Github Pages

Hexo 主題：Next

標籤和分類

語言

頭像

參考資料