### Persistent Segment Tree Initialization and Query Example (C++)

Source: https://cp-algorithms.com/data_structures/segment_tree

Demonstrates how to initialize a persistent Segment Tree from a vector `a` and then use it to find the 5th smallest element in a subarray. Assumes `MAX_VALUE` is defined and `a` is a pre-populated vector.

```cpp
// Assume MAX_VALUE is defined, e.g., const int MAX_VALUE = 100000;
// Assume 'a' is a std::vector<int> with input values.

int tl = 0, tr = MAX_VALUE + 1;
std::vector<Vertex*> roots;
roots.push_back(build(tl, tr));
for (int i = 0; i < a.size(); i++) {
    roots.push_back(update(roots.back(), tl, tr, a[i]));
}

// Example: find the 5th smallest number from the subarray [a[2], a[3], ..., a[19]]
// Note: roots[i] represents the tree after processing a[i-1].
// To query range [l, r], we use roots[r+1] and roots[l].
int result = find_kth(roots[2], roots[20], tl, tr, 5);

// The 'result' variable now holds the 5th smallest element in the specified range.
```

--------------------------------

### Install Dependencies and Serve Site Locally

Source: https://cp-algorithms.com/contrib

Installs the required dependencies for mkdocs using the provided script and then serves the mkdocs site locally for preview. Requires pip to be installed.

```bash
scripts/install-mkdocs.sh
mkdocs serve
```

--------------------------------

### Initialization and Execution of Closest Pair Algorithm (C++)

Source: https://cp-algorithms.com/geometry/nearest_points

Provides the setup code to run the closest pair algorithm. It resizes the auxiliary buffer `t` to match the number of points `n`, sorts the input points `a` by their x-coordinates using `cmp_x`, initializes `mindist` to a large value, and then calls the recursive function `rec` to find the closest pair within the entire range of points `[0, n)`. This code assumes `n` and `a` are already defined.

```cpp
t.resize(n);
sort(a.begin(), a.end(), cmp_x());
mindist = 1E20;
rec(0, n);

```

--------------------------------

### Topological Sort using DFS in C++

Source: https://cp-algorithms.com/graph/topological-sort

This C++ code implements topological sort for a directed acyclic graph (DAG) using Depth First Search (DFS). It assumes the graph is acyclic. The main function `topological_sort` initializes DFS variables, performs DFS starting from unvisited nodes, and reverses the result to get the topological order. The `dfs` function recursively visits neighbors and adds the current node to the result list after all its descendants have been visited.

```cpp
int n; // number of vertices
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> ans;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
        }
    }
    ans.push_back(v);
}

void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    reverse(ans.begin(), ans.end());
}

```

--------------------------------

### Find Cycle Start in Linked List (Java)

Source: https://cp-algorithms.com/others/tortoise_and_hare

Finds the starting node of a cycle in a linked list, assuming a cycle is already present. It resets the slow pointer to the head and moves both slow and fast pointers one step at a time until they meet. The meeting point is the start of the cycle.

```java
// Assuming there is a cycle present and slow and fast are point to their meeting point
slow = head;
while(slow!=fast){
    slow = slow.next;
    fast = fast.next;
}

return slow; // the starting point of the cycle.
```

--------------------------------

### Heavy-Light Decomposition Initialization (C++)

Source: https://cp-algorithms.com/graph/hld

Initializes data structures and performs DFS and decomposition for heavy-light decomposition. It calculates parent, depth, heavy child, and segment tree positions for each node. Assumes vertex 0 as the root.

```cpp
int dfs(int v, vector<vector<int>> const& adj) {
    int size = 1;
    int max_c_size = 0;
    for (int c : adj[v]) {
        if (c != parent[v]) {
            parent[c] = v, depth[c] = depth[v] + 1;
            int c_size = dfs(c, adj);
            size += c_size;
            if (c_size > max_c_size)
                max_c_size = c_size, heavy[v] = c;
        }
    }
    return size;
}

void decompose(int v, int h, vector<vector<int>> const& adj) {
    head[v] = h, pos[v] = cur_pos++;
    if (heavy[v] != -1)
        decompose(heavy[v], h, adj);
    for (int c : adj[v]) {
        if (c != parent[v] && c != heavy[v])
            decompose(c, c, adj);
    }
}

void init(vector<vector<int>> const& adj) {
    int n = adj.size();
    parent = vector<int>(n);
    depth = vector<int>(n);
    heavy = vector<int>(n, -1);
    head = vector<int>(n);
    pos = vector<int>(n);
    cur_pos = 0;

    dfs(0, adj);
    decompose(0, 0, adj);
}
```

--------------------------------

### Simulated Annealing Algorithm Template in C++

Source: https://cp-algorithms.com/num_methods/simulated_annealing

Provides a C++ template for the simulated annealing algorithm. It includes a placeholder 'state' class with essential methods like constructor, 'next()' for generating neighbor states, and 'E()' for calculating the energy of a state. The main 'simAnneal' function orchestrates the annealing process, managing temperature decay and state transitions.

```cpp
class state {
    public:
    state() {
        // Generate the initial state
    }
    state next() {
        state s_next;
        // Modify s_next to a random neighboring state
        return s_next;
    }
    double E() {
        // Implement the energy function here
    };
};


pair<double, state> simAnneal() {
    state s = state();
    state best = s;
    double T = 10000; // Initial temperature
    double u = 0.995; // decay rate
    double E = s.E();
    double E_next;
    double E_best = E;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    while (T > 1) {
        state next = s.next();
        E_next = next.E();
        if (P(E, E_next, T, rng)) {
            s = next;
            if (E_next < E_best) {
                best = s;
                E_best = E_next;
            }
            E = E_next;
        }
        T *= u;
    }
    return {E_best, best};
}

```

--------------------------------

### Output All Occurrences in Suffix Automaton (C++)

Source: https://cp-algorithms.com/string/suffix-automaton

This function recursively traverses the suffix automaton to output all occurrences of a pattern within a given string. It starts from a given state 'v' and its length 'P_length', printing the starting position of occurrences.

```cpp
void output_all_occurrences(int v, int P_length) {
    if (!st[v].is_clone)
        cout << st[v].first_pos - P_length + 1 << endl;
    for (int u : st[v].inv_link)
        output_all_occurrences(u, P_length);
}
```

--------------------------------

### 1D Interval Intersection Check in C++

Source: https://cp-algorithms.com/geometry/check-segments-intersection

Checks if two 1D intervals [a, b] and [c, d] intersect. It first ensures that the start of each interval is less than or equal to its end, then checks if the maximum of the start points is less than or equal to the minimum of the end points.

```cpp
bool inter1(long long a, long long b, long long c, long long d) {
    if (a > b)
        swap(a, b);
    if (c > d)
        swap(c, d);
    return max(a, c) <= min(b, d);
}
```

--------------------------------

### Generic DP Optimization Implementation in C++

Source: https://cp-algorithms.com/dynamic_programming/knuth-optimization

A generic C++ implementation demonstrating the dynamic programming optimization technique. This code calculates DP states and optimizes the search for the split point 'k' within a given range. It assumes the existence of a cost function C(i, j) and initializes base cases.

```cpp
int solve() {
    int N;
    ... // read N and input
    int dp[N][N], opt[N][N];

    auto C = [&](int i, int j) {
        ... // Implement cost function C.
    };

    for (int i = 0; i < N; i++) {
        opt[i][i] = i;
        ... // Initialize dp[i][i] according to the problem
    }

    for (int i = N-2; i >= 0; i--) {
        for (int j = i+1; j < N; j++) {
            int mn = INT_MAX;
            int cost = C(i, j);
            for (int k = opt[i][j-1]; k <= min(j-1, opt[i+1][j]); k++) {
                if (mn >= dp[i][k] + dp[k+1][j] + cost) {
                    opt[i][j] = k; 
                    mn = dp[i][k] + dp[k+1][j] + cost; 
                }
            }
            dp[i][j] = mn; 
        }
    }

    return dp[0][N-1];
}

```

--------------------------------

### Path Query with Heavy-Light Decomposition (C++)

Source: https://cp-algorithms.com/graph/hld

Answers path queries, such as finding the maximum value, using the precomputed heavy-light decomposition structures. It efficiently traverses heavy paths and uses segment tree queries to aggregate results.

```cpp
int query(int a, int b) {
    int res = 0;
    for (; head[a] != head[b]; b = parent[head[b]]) {
        if (depth[head[a]] > depth[head[b]])
            swap(a, b);
        int cur_heavy_path_max = segment_tree_query(pos[head[b]], pos[b]);
        res = max(res, cur_heavy_path_max);
    }
    if (depth[a] > depth[b])
        swap(a, b);
    int last_heavy_path_max = segment_tree_query(pos[a], pos[b]);
    res = max(res, last_heavy_path_max);
    return res;
}
```

--------------------------------

### Segment Tree Lazy Propagation for Range Assignment and Point Query (C++)

Source: https://cp-algorithms.com/data_structures/segment_tree

Implements the push, update, and get functions for a segment tree. The 'push' function propagates lazy updates down the tree. The 'update' function performs range assignments, marking nodes when a segment is fully covered. The 'get' function retrieves a value at a specific position, applying lazy updates as needed.

```C++
void push(int v) {
    if (marked[v]) {
        t[v*2] = t[v*2+1] = t[v];
        marked[v*2] = marked[v*2+1] = true;
        marked[v] = false;
    }
}

void update(int v, int tl, int tr, int l, int r, int new_val) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        t[v] = new_val;
        marked[v] = true;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), new_val);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, new_val);
    }
}

int get(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        return t[v];
    }
    push(v);
    int tm = (tl + tr) / 2;
    if (pos <= tm) 
        return get(v*2, tl, tm, pos);
    else
        return get(v*2+1, tm+1, tr, pos);
}
```

--------------------------------

### Compute Z-Function in C++

Source: https://cp-algorithms.com/string/z-function

Calculates the Z-function for a given string. The Z-function z[i] for a string s is the length of the longest common prefix between s and the suffix of s starting at index i. This implementation uses a linear-time approach.

```cpp
vector<int> z_function(string s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}
```

--------------------------------

### Heuristic Initial Matching and Kuhn's Algorithm Main Loop (C++)

Source: https://cp-algorithms.com/graph/kuhn_maximum_bipartite_matching

This C++ code snippet demonstrates an improved `main` function for Kuhn's algorithm. It first establishes an arbitrary matching using a simple heuristic by iterating through vertices and their edges. Subsequently, it refines this initial matching by calling `try_kuhn()` for vertices not yet included in the matching. This approach aims to speed up the overall process, especially for random graph structures.

```cpp
int main() {
    // ... reading the graph ...

    mt.assign(k, -1);
    vector<bool> used1(n, false);
    for (int v = 0; v < n; ++v) {
        for (int to : g[v]) {
            if (mt[to] == -1) {
                mt[to] = v;
                used1[v] = true;
                break;
            }
        }
    }
    for (int v = 0; v < n; ++v) {
        if (used1[v])
            continue;
        used.assign(n, false);
        try_kuhn(v);
    }

    for (int i = 0; i < k; ++i)
        if (mt[i] != -1)
            printf("%d %d\n", mt[i] + 1, i + 1);
}

```

--------------------------------

### Unbounded Knapsack DP Transition (C++)

Source: https://cp-algorithms.com/dynamic_programming/knapsack

This C++ code implements the dynamic programming solution for the unbounded knapsack problem. It iterates through items and possible weights, updating the maximum value that can be achieved. The inner loop's structure allows for items to be taken multiple times, which is characteristic of the unbounded knapsack problem.

```cpp
for (int i = 1; i <= n; i++)
  for (int j = w[i]; j <= W; j++)
    f[j] = max(f[j], f[j - w[i]] + v[i]);
```

--------------------------------

### Helper function to get Z-value in C++

Source: https://cp-algorithms.com/string/main_lorentz

Safely retrieves the Z-value for a given index from a Z-array. It handles out-of-bounds indices by returning 0, preventing potential errors during algorithm execution. This is used in conjunction with the `z_function`.

```cpp
int get_z(vector<int> const& z, int i) {
    if (0 <= i && i < (int)z.size())
        return z[i];
    else
        return 0;
}
```

--------------------------------

### Convex Polygon Preprocessing and Point-in-Polygon Test (C++)

Source: https://cp-algorithms.com/geometry/point-in-convex-polygon

Implements `prepare` to find the lexicographically smallest point and reorder vertices, and `pointInConvexPolygon` to check if a point is inside the polygon using binary search and triangle tests. It assumes points are sorted after preparation.

```cpp
vector<pt> seq;
pt translation;
int n;

bool pointInTriangle(pt a, pt b, pt c, pt point) {
    long long s1 = abs(a.cross(b, c));
    long long s2 = abs(point.cross(a, b)) + abs(point.cross(b, c)) + abs(point.cross(c, a));
    return s1 == s2;
}

void prepare(vector<pt> &points) {
    n = points.size();
    int pos = 0;
    for (int i = 1; i < n; i++) {
        if (lexComp(points[i], points[pos]))
            pos = i;
    }
    rotate(points.begin(), points.begin() + pos, points.end());

    n--;
    seq.resize(n);
    for (int i = 0; i < n; i++)
        seq[i] = points[i + 1] - points[0];
    translation = points[0];
}

bool pointInConvexPolygon(pt point) {
    point = point - translation;
    if (seq[0].cross(point) != 0 &&
            sgn(seq[0].cross(point)) != sgn(seq[0].cross(seq[n - 1])))
        return false;
    if (seq[n - 1].cross(point) != 0 &&
            sgn(seq[n - 1].cross(point)) != sgn(seq[n - 1].cross(seq[0])))
        return false;

    if (seq[0].cross(point) == 0)
        return seq[0].sqrLen() >= point.sqrLen();

    int l = 0, r = n - 1;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        int pos = mid;
        if (seq[pos].cross(point) >= 0)
            l = mid;
        else
            r = mid;
    }
    int pos = l;
    return pointInTriangle(seq[pos], seq[pos + 1], pt(0, 0), point);
}
```

--------------------------------

### Shortest Path Reconstruction (C++, Java)

Source: https://cp-algorithms.com/graph/breadth-first-search

Restores and displays the shortest path from a source vertex to a given vertex 'u' using the parent pointers generated during BFS. It handles cases where no path exists. Dependencies include the 'used' array and 'p' (parent) array from the BFS traversal.

```cpp
if (!used[u]) {
    cout << "No path!";
} else {
    vector<int> path;
    for (int v = u; v != -1; v = p[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    cout << "Path: ";
    for (int v : path)
        cout << v << " ";
}
```

```java
if (!used[u]) {
    System.out.println("No path!");
} else {
    ArrayList<Integer> path = new ArrayList<Integer>();
    for (int v = u; v != -1; v = p[v])
        path.add(v);
    Collections.reverse(path);
    for(int v : path)
        System.out.println(v);
}
```

--------------------------------

### Bitwise NOT Operator (~) Example

Source: https://cp-algorithms.com/algebra/bit-manipulation

Explains the bitwise complement (NOT) operation. This operator flips each bit of a number: 0 becomes 1, and 1 becomes 0. It's essential for inverting bit patterns.

```pseudo
n         = 01011000
--------------------
~n        = 10100111
```

--------------------------------

### Z-Function Implementation in C++

Source: https://cp-algorithms.com/string/main_lorentz

Computes the Z-array for a given string. The Z-array stores the length of the longest common prefix between the string and its suffixes starting at each index. This is a crucial component for many string algorithms, including the Main-Lorentz algorithm.

```cpp
vector<int> z_function(string const& s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r)
            z[i] = min(r-i+1, z[i-l]);
        while (i + z[i] < n && s[z[i]] == s[i+z[i]])
            z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}
```