---

# C++11 与算法基础讲义（算法部分）

---

## 第一部分：算法策略

### 1. 离散化 (Discretization)
离散化是一种将大范围、稀疏的数据映射到小范围、连续区间的技术。它在保持原有数值相对大小关系（大小、先后顺序）不变的前提下，极大地优化了空间和时间复杂度。

#### 1.1 算法步骤与 C++11 实现
1. 复制原数组，对其进行排序。
2. 使用 `std::unique` 去除重复元素。
3. 利用 `std::lower_bound` 进行二分查找，确定原数据在排好序的去重数组中的索引（通常从 $0$ 或 $1$ 开始）。

```cpp
#include <vector>
#include <algorithm>

// 将原向量 a 离散化，返回对应的紧凑索引向量（从 0 开始）
std::vector<int> discretize(const std::vector<int>& a) {
    std::vector<int> temp = a;
    std::sort(temp.begin(), temp.end());
    // std::unique 将重复元素移到末尾，并返回指向第一个重复元素的迭代器
    temp.erase(std::unique(temp.begin(), temp.end()), temp.end());
    
    std::vector<int> rank;
    rank.reserve(a.size());
    for (int x : a) {
        // std::lower_bound 寻找第一个大于等于 x 的元素，返回迭代器
        int idx = std::distance(temp.begin(), std::lower_bound(temp.begin(), temp.end(), x));
        rank.push_back(idx);
    }
    return rank;
}
```

---

### 2. 扫描线算法 (Sweep Line)
扫描线算法是计算几何和区间处理中的经典策略。其核心思想是将几何元素（如区间、矩形）的边界转化为“事件”（Event），然后用一条虚构的线（一维中为点，二维中为垂直线）按坐标顺序扫描，在扫描过程中维护当前状态。

#### 2.1 典型应用：区间合并/覆盖总长度
**问题**：给定 $N$ 个闭区间 $[l_i, r_i]$，求它们并集的总长度。
**状态维护**：将每个区间拆分为两个事件：左端点 $l_i$（事件值 $+1$）和右端点 $r_i$（事件值 $-1$）。将事件排序后进行扫描。用 `active_count` 记录当前被覆盖的区间层数。当 `active_count > 0` 时，累加相邻事件点之间的物理距离。

#### 2.2 C++11 代码实现
```cpp
#include <vector>
#include <algorithm>

struct Event {
    int pos;
    int type; // +1 表示区间开始，-1 表示区间结束
    bool operator<(const Event& other) const {
        return pos < other.pos;
    }
};

int interval_union_length(const std::vector<std::pair<int, int>>& intervals) {
    std::vector<Event> events;
    events.reserve(intervals.size() * 2);
    for (const auto& item : intervals) {
        events.push_back({item.first, 1});
        events.push_back({item.second, -1});
    }
    std::sort(events.begin(), events.end());

int total_length = 0;
    int active_count = 0;
    for (size_t i = 0; i < events.size(); ++i) {
        if (active_count > 0 && i > 0) {
            total_length += events[i].pos - events[i - 1].pos;
        }
        active_count += events[i].type;
    }
    return total_length;
}
```

---

## 第二部分：字符串算法

### 1. KMP 算法 (Knuth-Morris-Pratt)
KMP 算法用于在 $O(N+M)$ 时间内解决单模式串匹配问题。

#### 1.1 前缀函数 $\pi(i)$（即 `next` 数组）的递推推导
前缀函数 $\pi[i]$ 定义为：子串 $s[0..i]$ 中，最长的相等的真前缀与真后缀的长度。
设我们已经求出了 $\pi[0..i-1]$。现在要求 $\pi[i]$：
1. 记当前候选长度为 $j = \pi[i-1]$。
2. 如果 $s[i] == s[j]$，则说明匹配成功，$\pi[i] = j + 1$。
3. 如果 $s[i] \neq s[j]$，我们需要缩短候选长度 $j$。由于 $s[0..j-1]$ 是相等的，所以下一个可能匹配的最大长度是 $\pi[j-1]$。因此令 $j = \pi[j-1]$，重复此过程，直到匹配成功或者 $j = 0$。如果最后 $j=0$ 且仍不匹配，则 $\pi[i] = 0$。

#### 1.2 C++11 实现
```cpp
#include <string>
#include <vector>

// 计算前缀函数
std::vector<int> compute_prefix_function(const std::string& pattern) {
    int m = pattern.length();
    std::vector<int> pi(m, 0);
    for (int i = 1; i < m; ++i) {
        int j = pi[i - 1];
        while (j > 0 && pattern[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        pi[i] = j;
    }
    return pi;
}

// KMP 匹配，返回所有匹配成功的起始下标
std::vector<int> kmp_search(const std::string& text, const std::string& pattern) {
    std::vector<int> pi = compute_prefix_function(pattern);
    std::vector<int> matches;
    int n = text.length();
    int m = pattern.length();
    int j = 0; // 模式串的当前匹配位置
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == m) {
            matches.push_back(i - m + 1);
            j = pi[j - 1]; // 寻找下一个匹配
        }
    }
    return matches;
}
```

---

### 2. Manacher 算法
Manacher 算法用于在 $O(N)$ 时间内求解字符串中最长回文子串。

#### 2.1 算法性质与对称性状态转移
为了统一处理奇回文和偶回文，算法首先在字符间插入特殊占位符（如 `#`），使得变换后的字符串长度必为奇数。
设 $P[i]$ 表示以字符 $T[i]$ 为中心的最长回文半径（包含 $T[i]$ 自身）。
算法维护两个关键变量：
*   $R$：当前已探测到的所有回文子串所能覆盖的最右边界。
*   $C$：对应最右边界 $R$ 的回文中心。

对于当前要求解的 $P[i]$，若 $i < R$：
根据对称性，设 $i$ 关于 $C$ 的对称点为 $i' = 2C - i$。
*   **情况 1**：以 $i'$ 为中心的回文区域完全包含在以 $C$ 为中心的回文区域内（即 $i + P[i'] < R$），则由对称性可直接得出 $P[i] = P[i']$。
*   **情况 2**：以 $i'$ 为中心的回文区域有一部分超出了 $C$ 覆盖的范围（即 $i + P[i'] \ge R$），由于超出 $R$ 的部分未被探索，我们只能保证 $P[i]$ 至少为 $R - i$。随后需要以此为起点向外暴力匹配，并更新 $C$ 和 $R$。

#### 2.2 C++11 代码实现
```cpp
#include <string>
#include <vector>
#include <algorithm>

std::string preprocess(const std::string& s) {
    std::string t = "^";
    for (char c : s) {
        t += "#";
        t += c;
    }
    t += "#$";
    return t;
}

int longest_palindrome(const std::string& s) {
    std::string t = preprocess(s);
    int n = t.length();
    std::vector<int> p(n, 0);
    int C = 0, R = 0;
    int max_len = 0;

for (int i = 1; i < n - 1; ++i) {
        int i_mirror = 2 * C - i;
        if (R > i) {
            p[i] = std::min(R - i, p[i_mirror]);
        } else {
            p[i] = 0;
        }

// 尝试向外扩展
        while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) {
            p[i]++;
        }

// 如果超出了当前最右边界 R，则更新中心 C 和边界 R
        if (i + p[i] > R) {
            C = i;
            R = i + p[i];
        }
        max_len = std::max(max_len, p[i]);
    }
    return max_len;
}
```

---

## 第三部分：搜索与图论算法

### 1. 强连通分量 (Tarjan's SCC)
有向图的强连通分量（Strongly Connected Component, SCC）是指子图内任意两点均可互相到达的最大子图。Tarjan 算法基于深度优先搜索（DFS）树，利用两个关键数组在 $O(V+E)$ 时间内求出所有 SCC。

#### 1.1 核心概念
*   `dfn[u]`：节点 $u$ 的 DFS 发现时间步。
*   `low[u]`：从 $u$ 出发，通过 DFS 树边或最多一条非树边（且该边指向的节点仍在 DFS 栈中）所能到达的节点的最小 `dfn` 值。

当 DFS 遍历完毕节点 $u$ 的所有子树后，若发现 `dfn[u] == low[u]`，则表明 $u$ 是当前 SCC 的“根”。此时，在 DFS 栈中位于 $u$ 之上的所有元素连同 $u$ 一起构成一个强连通分量。

#### 1.2 C++11 实现
```cpp
#include <vector>
#include <stack>
#include <algorithm>

struct Tarjan {
    int n;
    std::vector<std::vector<int>> adj;
    std::vector<int> dfn, low;
    std::vector<bool> in_stack;
    std::stack<int> st;
    std::vector<std::vector<int>> sccs;
    int timer;

Tarjan(int nodes) : n(nodes), adj(nodes), dfn(nodes, -1), low(nodes, -1), in_stack(nodes, false), timer(0) {}

void add_edge(int u, int v) {
        adj[u].push_back(v);
    }

void dfs(int u) {
        dfn[u] = low[u] = ++timer;
        st.push(u);
        in_stack[u] = true;

for (int v : adj[u]) {
            if (dfn[v] == -1) {
                dfs(v);
                low[u] = std::min(low[u], low[v]);
            } else if (in_stack[v]) {
                low[u] = std::min(low[u], dfn[v]);
            }
        }

if (dfn[u] == low[u]) {
            std::vector<int> scc;
            while (true) {
                int curr = st.top();
                st.pop();
                in_stack[curr] = false;
                scc.push_back(curr);
                if (curr == u) break;
            }
            sccs.push_back(scc);
        }
    }

std::vector<std::vector<int>> run() {
        for (int i = 0; i < n; ++i) {
            if (dfn[i] == -1) dfs(i);
        }
        return sccs;
    }
};
```

---

### 2. 最近公共祖先 (LCA - 倍增法)
倍增法是一种利用二进制拆分快速向上跳转的 LCA 求解算法。其单次查询的时间复杂度为 $O(\log N)$，预处理复杂度为 $O(N \log N)$。

#### 2.1 状态设计与转移
*   `up[u][i]`：表示节点 $u$ 的第 $2^i$ 代祖先。
*   **状态转移方程**：$u$ 的第 $2^i$ 代祖先等于 $u$ 的第 $2^{i-1}$ 代祖先的第 $2^{i-1}$ 代祖先。即：
    $$up[u][i] = up[up[u][i-1]][i-1]$$

#### 2.2 C++11 实现
```cpp
#include <vector>
#include <cmath>

struct LCA {
    int n;
    int log_n;
    std::vector<std::vector<int>> adj;
    std::vector<std::vector<int>> up;
    std::vector<int> depth;

LCA(int nodes) : n(nodes), adj(nodes) {
        log_n = std::ceil(std::log2(n)) + 1;
        up.assign(n, std::vector<int>(log_n, 0));
        depth.assign(n, 0);
    }

void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

void dfs(int u, int p, int d) {
        depth[u] = d;
        up[u][0] = p;
        for (int i = 1; i < log_n; ++i) {
            up[u][i] = up[up[u][i-1]][i-1];
        }
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1);
            }
        }
    }

void init(int root = 0) {
        dfs(root, root, 0);
    }

int query(int u, int v) {
        if (depth[u] < depth[v]) std::swap(u, v);
        // 1. 将 u 提升到与 v 相同的深度
        for (int i = log_n - 1; i >= 0; --i) {
            if (depth[u] - (1 << i) >= depth[v]) {
                u = up[u][i];
            }
        }
        if (u == v) return u;
        // 2. 两个节点同时倍增向上跳
        for (int i = log_n - 1; i >= 0; --i) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }
};
```

---

## 第四部分：动态规划优化

### 1. 单调队列优化 (Monotonic Queue Optimization)
单调队列常用于优化具有如下形式的状态转移方程：
$$dp[i] = \min_{i-L \le j < i} \{ dp[j] + f(j) \} + g(i)$$
传统的暴力计算需要 $O(L)$ 的时间扫描决策点，总时间复杂度为 $O(N \cdot L)$。利用单调队列维护候选决策点，可将每次转移的均摊复杂度降至 $O(1)$，总复杂度降为 $O(N)$。

#### 1.1 队列维护性质与更新策略
我们使用双端队列 `std::deque`。队列中存储的是决策点的下标。我们需要保证队列中对应的价值序列 $val(j) = dp[j] + f(j)$ 是单调递增的（以求最小值为例）：
1.  **排除过期决策**：检查队头元素是否已经超出窗口范围 $[i-L, i-1]$。若超出，将其从队头弹出。
2.  **维护单调性**：在将新决策点 $i-1$ 加入队列前，比较其与队尾决策点的价值。若新决策点比队尾决策点更优，则队尾决策点永远不可能在未来成为最优解。我们将其从队尾不断弹出，直到队列为空或队尾决策点的值比新决策点小。
3.  **获取最优决策**：此时的队头元素即为当前区间内的最优点。

#### 1.2 C++11 实现
```cpp
#include <vector>
#include <deque>
#include <algorithm>

// 示例：求解 dp[i] = min_{i-L <= j < i} { dp[j] + val[j] } + cost[i]
std::vector<long long> solve_monotonic_dp(const std::vector<long long>& val, const std::vector<long long>& cost, int L) {
    int n = val.size();
    std::vector<long long> dp(n, 0);
    std::deque<int> dq; // 存储下标

dp[0] = cost[0];
    for (int i = 1; i < n; ++i) {
        // 1. 将上一个决策点 i-1 尝试加入队列
        long long new_val = dp[i - 1] + val[i - 1];
        while (!dq.empty() && (dp[dq.back()] + val[dq.back()]) >= new_val) {
            dq.pop_back();
        }
        dq.push_back(i - 1);

// 2. 剔除过期决策点
        while (!dq.empty() && dq.front() < i - L) {
            dq.pop_front();
        }

// 3. 转移
        dp[i] = (dp[dq.front()] + val[dq.front()]) + cost[i];
    }
    return dp;
}
```

---

## 第五部分：练习题与解析

### 练习题 1：KMP 算法的扩展应用（周期与边界）
**题目**：给定一个长度为 $N$ 的字符串 $S$，利用前缀函数 $\pi$ 判断其是否由某个子串重复多次拼接而成。若是，求出其最小重复周期的长度；若否，输出原字符串长度 $N$。

### 练习题 2：树上差分与最近公共祖先
**题目**：给定一棵包含 $N$ 个节点的树，初始时所有边的权值均为 $0$。现在给定 $M$ 次操作，每次操作将节点 $u$ 到 $v$ 的路径上所有边的权值都加 $1$。
请输出最终所有操作结束后，每条边上的权值。

---

### 详细解析与答案

#### 习题 1 解析：
*   **性质定理**：字符串 $S$ 具有长度为 $k$ 的循环元的充要条件是 $k$ 整除 $N$，且最长相等前后缀长度满足 $\pi[N-1] = N - k$。
*   **证明推导**：
    若 $S$ 存在循环节 $T$（长度为 $k$），则 $S$ 可以表示为 $T T \dots T$（共 $c$ 个）。
    显然其前 $c-1$ 个循环节与后 $c-1$ 个循环节完全相同，构成长度为 $N-k$ 的相等前后缀。
    因此，若 $N - \pi[N-1]$ 能整除 $N$，且 $\pi[N-1] > 0$，则最小重复周期长度为 $N - \pi[N-1]$。

*   **C++11 验证函数**：
    ```cpp
    #include <iostream>
    #include <string>
    #include <vector>

int get_minimum_period(const std::string& s) {
        int n = s.length();
        if (n == 0) return 0;
        // 计算前缀函数 pi
        std::vector<int> pi(n, 0);
        for (int i = 1; i < n; ++i) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];
            if (s[i] == s[j]) ++j;
            pi[i] = j;
        }

int max_border = pi[n - 1];
        int k = n - max_border;
        if (max_border > 0 && n % k == 0) {
            return k; // 存在循环，返回最小周期
        }
        return n; // 无循环，返回原长
    }
    ```

#### 习题 2 解析：
这是一个典型的**边差分**问题。我们可以通过树上差分将路径修改操作的单次复杂度降至 $O(1)$，最后通过一次深度优先搜索自底向上合并结果。

1.  **树上边差分原理**：
    对于将路径 $(u, v)$ 上的边权加 $1$ 的操作：
    设 $p = \text{LCA}(u, v)$。
    我们在节点的差分数组 `diff` 上进行如下标记：
    *   `diff[u] += 1`
    *   `diff[v] += 1`
    *   `diff[p] -= 2`
    
    *注意*：由于是**边权**而不是点权，LCA 节点 $p$ 的上方边不应被修改，因此我们要对 $p$ 的差分值减 $2$。
2.  **结果合并**：
    在差分标记完成后，通过一次自底向上的 DFS（即后序遍历）。每个节点与其子树中所有节点的差分值之和，即为该节点与其父节点相连那条边的最终权值。

3.  **C++11 完整合并逻辑实现**：
    ```cpp
    #include <vector>
    #include <iostream>

struct Edge {
        int to;
        int id; // 边的编号
    };

struct TreeDifference {
        int n;
        std::vector<std::vector<Edge>> adj;
        std::vector<int> diff;
        std::vector<int> edge_weights; // 存储最终每条边的权值

TreeDifference(int nodes) : n(nodes), adj(nodes), diff(nodes, 0), edge_weights(nodes - 1, 0) {}

void add_edge(int u, int v, int edge_id) {
            adj[u].push_back({v, edge_id});
            adj[v].push_back({u, edge_id});
        }

void update_path(int u, int v, int lca) {
            diff[u] += 1;
            diff[v] += 1;
            diff[lca] -= 2;
        }

// 自底向上回溯合并差分值
        int dfs_collect(int u, int p, int edge_to_parent_id) {
            int current_sum = diff[u];
            for (const auto& edge : adj[u]) {
                if (edge.to != p) {
                    current_sum += dfs_collect(edge.to, u, edge.id);
                }
            }
            if (edge_to_parent_id != -1) {
                edge_weights[edge_to_parent_id] = current_sum;
            }
            return current_sum;
        }

void solve(int root = 0) {
            dfs_collect(root, -1, -1);
        }
    };
```

C++11 与算法基础讲义（算法部分）

第一部分：算法策略

1. 离散化 (Discretization)

离散化是一种将大范围、稀疏的数据映射到小范围、连续区间的技术。它在保持原有数值相对大小关系（大小、先后顺序）不变的前提下，极大地优化了空间和时间复杂度。

1.1 算法步骤与 C++11 实现

复制原数组，对其进行排序。
使用 std::unique 去除重复元素。
利用 std::lower_bound 进行二分查找，确定原数据在排好序的去重数组中的索引（通常从 $0$ 或 $1$ 开始）。

#include <vector>
#include <algorithm>

// 将原向量 a 离散化，返回对应的紧凑索引向量（从 0 开始）
std::vector<int> discretize(const std::vector<int>& a) {
    std::vector<int> temp = a;
    std::sort(temp.begin(), temp.end());
    // std::unique 将重复元素移到末尾，并返回指向第一个重复元素的迭代器
    temp.erase(std::unique(temp.begin(), temp.end()), temp.end());

    std::vector<int> rank;
    rank.reserve(a.size());
    for (int x : a) {
        // std::lower_bound 寻找第一个大于等于 x 的元素，返回迭代器
        int idx = std::distance(temp.begin(), std::lower_bound(temp.begin(), temp.end(), x));
        rank.push_back(idx);
    }
    return rank;
}

2. 扫描线算法 (Sweep Line)

扫描线算法是计算几何和区间处理中的经典策略。其核心思想是将几何元素（如区间、矩形）的边界转化为“事件”（Event），然后用一条虚构的线（一维中为点，二维中为垂直线）按坐标顺序扫描，在扫描过程中维护当前状态。

2.1 典型应用：区间合并/覆盖总长度

问题：给定 $N$ 个闭区间 $[l_i, r_i]$，求它们并集的总长度。 状态维护：将每个区间拆分为两个事件：左端点 $l_i$（事件值 $+1$）和右端点 $r_i$（事件值 $-1$）。将事件排序后进行扫描。用 active_count 记录当前被覆盖的区间层数。当 active_count > 0 时，累加相邻事件点之间的物理距离。

2.2 C++11 代码实现

#include <vector>
#include <algorithm>

struct Event {
    int pos;
    int type; // +1 表示区间开始，-1 表示区间结束
    bool operator<(const Event& other) const {
        return pos < other.pos;
    }
};

int interval_union_length(const std::vector<std::pair<int, int>>& intervals) {
    std::vector<Event> events;
    events.reserve(intervals.size() * 2);
    for (const auto& item : intervals) {
        events.push_back({item.first, 1});
        events.push_back({item.second, -1});
    }
    std::sort(events.begin(), events.end());

    int total_length = 0;
    int active_count = 0;
    for (size_t i = 0; i < events.size(); ++i) {
        if (active_count > 0 && i > 0) {
            total_length += events[i].pos - events[i - 1].pos;
        }
        active_count += events[i].type;
    }
    return total_length;
}

第二部分：字符串算法

1. KMP 算法 (Knuth-Morris-Pratt)

KMP 算法用于在 $O(N+M)$ 时间内解决单模式串匹配问题。

1.1 前缀函数 $\pi(i)$（即 `next` 数组）的递推推导

前缀函数 $\pi[i]$ 定义为：子串 $s[0..i]$ 中，最长的相等的真前缀与真后缀的长度。设我们已经求出了 $\pi[0..i-1]$。现在要求 $\pi[i]$： 1. 记当前候选长度为 $j = \pi[i-1]$。 2. 如果 $s[i] == s[j]$，则说明匹配成功，$\pi[i] = j + 1$。 3. 如果 $s[i] \neq s[j]$，我们需要缩短候选长度 $j$。由于 $s[0..j-1]$ 是相等的，所以下一个可能匹配的最大长度是 $\pi[j-1]$。因此令 $j = \pi[j-1]$，重复此过程，直到匹配成功或者 $j = 0$。如果最后 $j=0$ 且仍不匹配，则 $\pi[i] = 0$。

1.2 C++11 实现

#include <string>
#include <vector>

// 计算前缀函数
std::vector<int> compute_prefix_function(const std::string& pattern) {
    int m = pattern.length();
    std::vector<int> pi(m, 0);
    for (int i = 1; i < m; ++i) {
        int j = pi[i - 1];
        while (j > 0 && pattern[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            ++j;
        }
        pi[i] = j;
    }
    return pi;
}

// KMP 匹配，返回所有匹配成功的起始下标
std::vector<int> kmp_search(const std::string& text, const std::string& pattern) {
    std::vector<int> pi = compute_prefix_function(pattern);
    std::vector<int> matches;
    int n = text.length();
    int m = pattern.length();
    int j = 0; // 模式串的当前匹配位置
    for (int i = 0; i < n; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) {
            ++j;
        }
        if (j == m) {
            matches.push_back(i - m + 1);
            j = pi[j - 1]; // 寻找下一个匹配
        }
    }
    return matches;
}

2. Manacher 算法

Manacher 算法用于在 $O(N)$ 时间内求解字符串中最长回文子串。

2.1 算法性质与对称性状态转移

为了统一处理奇回文和偶回文，算法首先在字符间插入特殊占位符（如 #），使得变换后的字符串长度必为奇数。设 $P[i]$ 表示以字符 $T[i]$ 为中心的最长回文半径（包含 $T[i]$ 自身）。算法维护两个关键变量： * $R$：当前已探测到的所有回文子串所能覆盖的最右边界。 * $C$：对应最右边界 $R$ 的回文中心。

对于当前要求解的 $P[i]$，若 $i < R$：根据对称性，设 $i$ 关于 $C$ 的对称点为 $i' = 2C - i$。 * 情况 1：以 $i'$ 为中心的回文区域完全包含在以 $C$ 为中心的回文区域内（即 $i + P[i'] < R$），则由对称性可直接得出 $P[i] = P[i']$。 * 情况 2：以 $i'$ 为中心的回文区域有一部分超出了 $C$ 覆盖的范围（即 $i + P[i'] \ge R$），由于超出 $R$ 的部分未被探索，我们只能保证 $P[i]$ 至少为 $R - i$。随后需要以此为起点向外暴力匹配，并更新 $C$ 和 $R$。

2.2 C++11 代码实现

#include <string>
#include <vector>
#include <algorithm>

std::string preprocess(const std::string& s) {
    std::string t = "^";
    for (char c : s) {
        t += "#";
        t += c;
    }
    t += "#$";
    return t;
}

int longest_palindrome(const std::string& s) {
    std::string t = preprocess(s);
    int n = t.length();
    std::vector<int> p(n, 0);
    int C = 0, R = 0;
    int max_len = 0;

    for (int i = 1; i < n - 1; ++i) {
        int i_mirror = 2 * C - i;
        if (R > i) {
            p[i] = std::min(R - i, p[i_mirror]);
        } else {
            p[i] = 0;
        }

        // 尝试向外扩展
        while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) {
            p[i]++;
        }

        // 如果超出了当前最右边界 R，则更新中心 C 和边界 R
        if (i + p[i] > R) {
            C = i;
            R = i + p[i];
        }
        max_len = std::max(max_len, p[i]);
    }
    return max_len;
}

第三部分：搜索与图论算法

1. 强连通分量 (Tarjan's SCC)

有向图的强连通分量（Strongly Connected Component, SCC）是指子图内任意两点均可互相到达的最大子图。Tarjan 算法基于深度优先搜索（DFS）树，利用两个关键数组在 $O(V+E)$ 时间内求出所有 SCC。

1.1 核心概念

dfn[u]：节点 $u$ 的 DFS 发现时间步。
low[u]：从 $u$ 出发，通过 DFS 树边或最多一条非树边（且该边指向的节点仍在 DFS 栈中）所能到达的节点的最小 dfn 值。

当 DFS 遍历完毕节点 $u$ 的所有子树后，若发现 dfn[u] == low[u]，则表明 $u$ 是当前 SCC 的“根”。此时，在 DFS 栈中位于 $u$ 之上的所有元素连同 $u$ 一起构成一个强连通分量。

1.2 C++11 实现

#include <vector>
#include <stack>
#include <algorithm>

struct Tarjan {
    int n;
    std::vector<std::vector<int>> adj;
    std::vector<int> dfn, low;
    std::vector<bool> in_stack;
    std::stack<int> st;
    std::vector<std::vector<int>> sccs;
    int timer;

    Tarjan(int nodes) : n(nodes), adj(nodes), dfn(nodes, -1), low(nodes, -1), in_stack(nodes, false), timer(0) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
    }

    void dfs(int u) {
        dfn[u] = low[u] = ++timer;
        st.push(u);
        in_stack[u] = true;

        for (int v : adj[u]) {
            if (dfn[v] == -1) {
                dfs(v);
                low[u] = std::min(low[u], low[v]);
            } else if (in_stack[v]) {
                low[u] = std::min(low[u], dfn[v]);
            }
        }

        if (dfn[u] == low[u]) {
            std::vector<int> scc;
            while (true) {
                int curr = st.top();
                st.pop();
                in_stack[curr] = false;
                scc.push_back(curr);
                if (curr == u) break;
            }
            sccs.push_back(scc);
        }
    }

    std::vector<std::vector<int>> run() {
        for (int i = 0; i < n; ++i) {
            if (dfn[i] == -1) dfs(i);
        }
        return sccs;
    }
};

2. 最近公共祖先 (LCA - 倍增法)

倍增法是一种利用二进制拆分快速向上跳转的 LCA 求解算法。其单次查询的时间复杂度为 $O(\log N)$，预处理复杂度为 $O(N \log N)$。

2.1 状态设计与转移

up[u][i]：表示节点 $u$ 的第 $2^i$ 代祖先。
状态转移方程：$u$ 的第 $2^i$ 代祖先等于 $u$ 的第 $2^{i-1}$ 代祖先的第 $2^{i-1}$ 代祖先。即： $$up[u][i] = up[up[u][i-1]][i-1]$$

2.2 C++11 实现

#include <vector>
#include <cmath>

struct LCA {
    int n;
    int log_n;
    std::vector<std::vector<int>> adj;
    std::vector<std::vector<int>> up;
    std::vector<int> depth;

    LCA(int nodes) : n(nodes), adj(nodes) {
        log_n = std::ceil(std::log2(n)) + 1;
        up.assign(n, std::vector<int>(log_n, 0));
        depth.assign(n, 0);
    }

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs(int u, int p, int d) {
        depth[u] = d;
        up[u][0] = p;
        for (int i = 1; i < log_n; ++i) {
            up[u][i] = up[up[u][i-1]][i-1];
        }
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1);
            }
        }
    }

    void init(int root = 0) {
        dfs(root, root, 0);
    }

    int query(int u, int v) {
        if (depth[u] < depth[v]) std::swap(u, v);
        // 1. 将 u 提升到与 v 相同的深度
        for (int i = log_n - 1; i >= 0; --i) {
            if (depth[u] - (1 << i) >= depth[v]) {
                u = up[u][i];
            }
        }
        if (u == v) return u;
        // 2. 两个节点同时倍增向上跳
        for (int i = log_n - 1; i >= 0; --i) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }
};

第四部分：动态规划优化

1. 单调队列优化 (Monotonic Queue Optimization)

单调队列常用于优化具有如下形式的状态转移方程： $$dp[i] = \min_{i-L \le j < i} { dp[j] + f(j) } + g(i)$$ 传统的暴力计算需要 $O(L)$ 的时间扫描决策点，总时间复杂度为 $O(N \cdot L)$。利用单调队列维护候选决策点，可将每次转移的均摊复杂度降至 $O(1)$，总复杂度降为 $O(N)$。

1.1 队列维护性质与更新策略

我们使用双端队列 std::deque。队列中存储的是决策点的下标。我们需要保证队列中对应的价值序列 $val(j) = dp[j] + f(j)$ 是单调递增的（以求最小值为例）： 1. 排除过期决策：检查队头元素是否已经超出窗口范围 $[i-L, i-1]$。若超出，将其从队头弹出。 2. 维护单调性：在将新决策点 $i-1$ 加入队列前，比较其与队尾决策点的价值。若新决策点比队尾决策点更优，则队尾决策点永远不可能在未来成为最优解。我们将其从队尾不断弹出，直到队列为空或队尾决策点的值比新决策点小。 3. 获取最优决策：此时的队头元素即为当前区间内的最优点。

1.2 C++11 实现

#include <vector>
#include <deque>
#include <algorithm>

// 示例：求解 dp[i] = min_{i-L <= j < i} { dp[j] + val[j] } + cost[i]
std::vector<long long> solve_monotonic_dp(const std::vector<long long>& val, const std::vector<long long>& cost, int L) {
    int n = val.size();
    std::vector<long long> dp(n, 0);
    std::deque<int> dq; // 存储下标

    dp[0] = cost[0];
    for (int i = 1; i < n; ++i) {
        // 1. 将上一个决策点 i-1 尝试加入队列
        long long new_val = dp[i - 1] + val[i - 1];
        while (!dq.empty() && (dp[dq.back()] + val[dq.back()]) >= new_val) {
            dq.pop_back();
        }
        dq.push_back(i - 1);

        // 2. 剔除过期决策点
        while (!dq.empty() && dq.front() < i - L) {
            dq.pop_front();
        }

        // 3. 转移
        dp[i] = (dp[dq.front()] + val[dq.front()]) + cost[i];
    }
    return dp;
}

第五部分：练习题与解析

练习题 1：KMP 算法的扩展应用（周期与边界）

题目：给定一个长度为 $N$ 的字符串 $S$，利用前缀函数 $\pi$ 判断其是否由某个子串重复多次拼接而成。若是，求出其最小重复周期的长度；若否，输出原字符串长度 $N$。

练习题 2：树上差分与最近公共祖先

题目：给定一棵包含 $N$ 个节点的树，初始时所有边的权值均为 $0$。现在给定 $M$ 次操作，每次操作将节点 $u$ 到 $v$ 的路径上所有边的权值都加 $1$。请输出最终所有操作结束后，每条边上的权值。

详细解析与答案

习题 1 解析：

性质定理：字符串 $S$ 具有长度为 $k$ 的循环元的充要条件是 $k$ 整除 $N$，且最长相等前后缀长度满足 $\pi[N-1] = N - k$。
证明推导：若 $S$ 存在循环节 $T$（长度为 $k$），则 $S$ 可以表示为 $T T \dots T$（共 $c$ 个）。显然其前 $c-1$ 个循环节与后 $c-1$ 个循环节完全相同，构成长度为 $N-k$ 的相等前后缀。因此，若 $N - \pi[N-1]$ 能整除 $N$，且 $\pi[N-1] > 0$，则最小重复周期长度为 $N - \pi[N-1]$。
C++11 验证函数： ```cpp #include #include #include

int get_minimum_period(const std::string& s) { int n = s.length(); if (n == 0) return 0; // 计算前缀函数 pi std::vector pi(n, 0); for (int i = 1; i < n; ++i) { int j = pi[i - 1]; while (j > 0 && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]) ++j; pi[i] = j; }
```
int max_border = pi[n - 1];
int k = n - max_border;
if (max_border > 0 && n % k == 0) {
    return k; // 存在循环，返回最小周期
}
return n; // 无循环，返回原长
```
} ```

习题 2 解析：

这是一个典型的边差分问题。我们可以通过树上差分将路径修改操作的单次复杂度降至 $O(1)$，最后通过一次深度优先搜索自底向上合并结果。

树上边差分原理：对于将路径 $(u, v)$ 上的边权加 $1$ 的操作：设 $p = \text{LCA}(u, v)$。我们在节点的差分数组 diff 上进行如下标记：
- diff[u] += 1
- diff[v] += 1
- diff[p] -= 2
注意：由于是边权而不是点权，LCA 节点 $p$ 的上方边不应被修改，因此我们要对 $p$ 的差分值减 $2$。 2. 结果合并：在差分标记完成后，通过一次自底向上的 DFS（即后序遍历）。每个节点与其子树中所有节点的差分值之和，即为该节点与其父节点相连那条边的最终权值。

C++11 完整合并逻辑实现： ```cpp #include #include

struct Edge { int to; int id; // 边的编号 };

struct TreeDifference { int n; std::vector> adj; std::vector diff; std::vector edge_weights; // 存储最终每条边的权值

TreeDifference(int nodes) : n(nodes), adj(nodes), diff(nodes, 0), edge_weights(nodes - 1, 0) {}

void add_edge(int u, int v, int edge_id) {
    adj[u].push_back({v, edge_id});
    adj[v].push_back({u, edge_id});
}

void update_path(int u, int v, int lca) {
    diff[u] += 1;
    diff[v] += 1;
    diff[lca] -= 2;
}

// 自底向上回溯合并差分值
int dfs_collect(int u, int p, int edge_to_parent_id) {
    int current_sum = diff[u];
    for (const auto& edge : adj[u]) {
        if (edge.to != p) {
            current_sum += dfs_collect(edge.to, u, edge.id);
        }
    }
    if (edge_to_parent_id != -1) {
        edge_weights[edge_to_parent_id] = current_sum;
    }
    return current_sum;
}

void solve(int root = 0) {
    dfs_collect(root, -1, -1);
}

}; ```

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

提高组大纲2.2.4 算法

C++11 与算法基础讲义（算法部分）

第一部分：算法策略

1. 离散化 (Discretization)

1.1 算法步骤与 C++11 实现

2. 扫描线算法 (Sweep Line)

2.1 典型应用：区间合并/覆盖总长度

2.2 C++11 代码实现

第二部分：字符串算法

1. KMP 算法 (Knuth-Morris-Pratt)

1.1 前缀函数 $\pi(i)$（即 next 数组）的递推推导

1.2 C++11 实现

2. Manacher 算法

2.1 算法性质与对称性状态转移

2.2 C++11 代码实现

第三部分：搜索与图论算法

1. 强连通分量 (Tarjan's SCC)

1.1 核心概念

1.2 C++11 实现

2. 最近公共祖先 (LCA - 倍增法)

2.1 状态设计与转移

2.2 C++11 实现

第四部分：动态规划优化

1. 单调队列优化 (Monotonic Queue Optimization)

1.1 队列维护性质与更新策略

1.2 C++11 实现

第五部分：练习题与解析

练习题 1：KMP 算法的扩展应用（周期与边界）

练习题 2：树上差分与最近公共祖先

详细解析与答案

习题 1 解析：

习题 2 解析：

1.1 前缀函数 $\pi(i)$（即 `next` 数组）的递推推导