Data Structures

Mo's Algorithm

Standard Mo's Algorithm

Used to solve problems like P1494 [National Training Team] Little Z's Socks.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 200010;

struct Query {
    int l, r, idx;
};

struct Fraction {
    int numerator, denominator;
};

int n, qCount;
int arr[MAXN], blockStart[MAXN], blockEnd[MAXN], freq[MAXN], blockId[MAXN];
int currentSum = 0;
Query queries[MAXN];
Fraction results[MAXN];

bool compareQueries(const Query& a, const Query& b) {
    if (blockId[a.l] != blockId[b.l]) 
        return blockId[a.l] < blockId[b.l];
    return (blockId[a.l] & 1) ? (a.r < b.r) : (a.r > b.r);
}

void addElement(int pos) {
    currentSum += 2 * freq[arr[pos]];
    freq[arr[pos]]++;
}

void removeElement(int pos) {
    freq[arr[pos]]--;
    currentSum -= 2 * freq[arr[pos]];
}

long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> qCount;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    for (int i = 1; i <= qCount; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].idx = i;
    }

    int blockSize = sqrt(qCount);
    int totalBlocks = (n + blockSize - 1) / blockSize;
    for (int i = 1; i <= totalBlocks; ++i) {
        blockStart[i] = (i - 1) * blockSize + 1;
        blockEnd[i] = min(i * blockSize, n);
    }
    for (int i = 1; i <= totalBlocks; ++i)
        for (int j = blockStart[i]; j <= blockEnd[i]; ++j)
            blockId[j] = i;

    sort(queries + 1, queries + qCount + 1, compareQueries);

    int curL = 1, curR = 0;
    for (int i = 1; i <= qCount; ++i) {
        if (queries[i].l == queries[i].r) {
            results[queries[i].idx] = {0, 1};
            continue;
        }
        while (curL > queries[i].l) addElement(--curL);
        while (curR < queries[i].r) addElement(++curR);
        while (curL < queries[i].l) removeElement(curL++);
        while (curR > queries[i].r) removeElement(curR--);

        long long totalPairs = 1LL * (curR - curL + 1) * (curR - curL);
        long long validPairs = currentSum;
        long long g = gcd(totalPairs, validPairs);
        results[queries[i].idx] = {(int)(validPairs / g), (int)(totalPairs / g)};
    }

    for (int i = 1; i <= qCount; ++i)
        printf("%d/%d\n", results[i].numerator, results[i].denominator);
    return 0;
}

Tree Mo's Algorithm

Computes the median of weights along the shortest path between two nodes in a tree.

Key idea: Convert the tree into an Euler Tour (parenthesis sequence). Each node appears twice—once when entering (in[u]) and once when leaving (out[u]).

For query (u, v):

• If u is not an ancestor of v, the path corresponds to interval [out[u], in[v]].
• If u is an ancestor of v, the path corresponds to [in[u], in[v]], excluding the part outside the subtree.

During Mo’s updates, toggle inclusion of a node based on its current frequency parity.

void toggle(int node, bool add) {
    if (used[node] & 1) remove(node);
    else insert(node);
    used[node] += add ? 1 : -1;
}

Full implementation involves buildign the Euler Tour, handling queries with adjusted intervals, and maintaining a block-based structure for efficient median retrieval.

Graph Theory

Tree Fundamentals

Tree Centroid

The centroid minimizes the size of the largest connected component after removal.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50010;
vector<int> adj[MAXN];
int subtreeSize[MAXN], maxSubtree[MAXN], centroid, totalNodes;
long long totalDist = 0, depth[MAXN];

void findCentroid(int u, int parent) {
    subtreeSize[u] = 1;
    maxSubtree[u] = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        findCentroid(v, u);
        subtreeSize[u] += subtreeSize[v];
        maxSubtree[u] = max(maxSubtree[u], subtreeSize[v]);
    }
    maxSubtree[u] = max(maxSubtree[u], totalNodes - subtreeSize[u]);
    if (maxSubtree[u] < maxSubtree[centroid])
        centroid = u;
}

void computeDepths(int u, int parent) {
    for (int v : adj[u]) {
        if (v == parent) continue;
        depth[v] = depth[u] + 1;
        computeDepths(v, u);
    }
}

int main() {
    cin >> totalNodes;
    for (int i = 1; i < totalNodes; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    maxSubtree[0] = INT_MAX;
    findCentroid(1, 0);
    computeDepths(centroid, 0);
    for (int i = 1; i <= totalNodes; ++i)
        totalDist += depth[i];
    cout << centroid << " " << totalDist << endl;
    return 0;
}

Minimum Spanning Tree (MST)

Prim’s Algorithm (Naive)

Time complexity: $O(n^2)$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
const int INF = 1e9;

vector<pair<int, int>> graph[MAXN];
int minEdge[MAXN], visited[MAXN];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }

    fill(minEdge, minEdge + n + 1, INF);
    minEdge[1] = 0;
    long long totalWeight = 0;

    for (int i = 1; i <= n; ++i) {
        int u = -1;
        for (int j = 1; j <= n; ++j)
            if (!visited[j] && (u == -1 || minEdge[j] < minEdge[u]))
                u = j;
        if (minEdge[u] == INF) { cout << "orz"; return 0; }
        visited[u] = 1;
        totalWeight += minEdge[u];
        for (auto [v, w] : graph[u])
            if (!visited[v] && w < minEdge[v])
                minEdge[v] = w;
    }
    cout << totalWeight << endl;
    return 0;
}

Kruskal’s Algorithm

Time complexity: $O(m \log m)$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;

struct Edge { int u, v, w; };
Edge edges[MAXN];
int parent[MAXN];

int findRoot(int x) { return parent[x] == x ? x : parent[x] = findRoot(parent[x]); }

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    for (int i = 1; i <= n; ++i) parent[i] = i;
    sort(edges + 1, edges + m + 1, [](const Edge& a, const Edge& b) { return a.w < b.w; });

    long long total = 0; int count = 0;
    for (int i = 1; i <= m; ++i) {
        int ru = findRoot(edges[i].u), rv = findRoot(edges[i].v);
        if (ru != rv) {
            parent[ru] = rv;
            total += edges[i].w;
            if (++count == n - 1) break;
        }
    }
    cout << (count == n - 1 ? total : -1) << endl;
    return 0;
}

Lowest Common Ancestor (LCA)

Binary Lifting

Preprocessing: $O(n \log n)$, Query: $O(\log n)$

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000010;
const int LOG = 20;

vector<int> tree[MAXN];
int depth[MAXN], up[MAXN][LOG];

void dfs(int u, int parent) {
    depth[u] = depth[parent] + 1;
    up[u][0] = parent;
    for (int i = 1; i < LOG; ++i)
        up[u][i] = up[up[u][i-1]][i-1];
    for (int v : tree[u])
        if (v != parent) dfs(v, u);
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG - 1; i >= 0; --i)
        if (depth[u] - (1 << i) >= depth[v])
            u = up[u][i];
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; --i)
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
}

int main() {
    int n, m, root; cin >> n >> m >> root;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(root, 0);
    while (m--) {
        int u, v; cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
    return 0;
}

Shortest Path Algorithms

Dijkstra’s Algorithm

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200010;
const ll INF = 1e18;

vector<pair<int, int>> adj[MAXN];
ll dist[MAXN];
bool visited[MAXN];

int main() {
    int n, m, start; cin >> n >> m >> start;
    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
    }

    fill(dist, dist + n + 1, INF);
    dist[start] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.emplace(0, start);

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (auto [v, w] : adj[u])
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
    }

    for (int i = 1; i <= n; ++i)
        cout << (dist[i] == INF ? -1 : dist[i]) << ' ';
    return 0;
}

Connectivity

Articulation Points

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;

vector<int> graph[MAXN];
int disc[MAXN], low[MAXN], timer;
bool isArticulation[MAXN];

void findArticulationPoints(int u, int parent) {
    disc[u] = low[u] = ++timer;
    int children = 0;
    for (int v : graph[u]) {
        if (v == parent) continue;
        if (!disc[v]) {
            children++;
            findArticulationPoints(v, u);
            low[u] = min(low[u], low[v]);
            if (parent != -1 && low[v] >= disc[u])
                isArticulation[u] = true;
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
    if (parent == -1 && children > 1)
        isArticulation[u] = true;
}

int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)
        if (!disc[i])
            findArticulationPoints(i, -1);
    vector<int> points;
    for (int i = 1; i <= n; ++i)
        if (isArticulation[i]) points.push_back(i);
    cout << points.size() << '\n';
    for (int x : points) cout << x << ' ';
    return 0;
}

Mathematics

Gaussian Elimination

Solves linear systems modulo floating-point tolerance.

#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-8;
double matrix[110][110];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n + 1; ++j)
            cin >> matrix[i][j];

    int rank = 1;
    for (int col = 1; col <= n; ++col) {
        int pivot = rank;
        for (int row = rank + 1; row <= n; ++row)
            if (abs(matrix[row][col]) > abs(matrix[pivot][col]))
                pivot = row;
        if (abs(matrix[pivot][col]) < EPS) continue;

        for (int j = col; j <= n + 1; ++j)
            swap(matrix[rank][j], matrix[pivot][j]);

        double factor = matrix[rank][col];
        for (int j = col; j <= n + 1; ++j)
            matrix[rank][j] /= factor;

        for (int row = 1; row <= n; ++row) {
            if (row != rank && abs(matrix[row][col]) > EPS) {
                double coef = matrix[row][col];
                for (int j = col; j <= n + 1; ++j)
                    matrix[row][j] -= coef * matrix[rank][j];
            }
        }
        rank++;
    }

    if (rank <= n) {
        for (int i = rank; i <= n; ++i)
            if (abs(matrix[i][n+1]) > EPS) {
                cout << "-1\n"; return 0;
            }
        cout << "0\n"; return 0;
    }

    for (int i = 1; i <= n; ++i)
        printf("x%d=%.2f\n", i, matrix[i][n+1]);
    return 0;
}

Extended Chinese Remainder Theorem (ECRT)

#include <bits/stdc++.h>
using namespace std;
typedef __int128_t int128;

int128 exgcd(int128 a, int128 b, int128& x, int128& y) {
    if (!b) { x = 1; y = 0; return a; }
    int128 d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    int n; cin >> n;
    vector<int128> moduli(n), remainders(n);
    for (int i = 0; i < n; ++i) cin >> moduli[i] >> remainders[i];

    int128 currentMod = moduli[0], currentRem = remainders[0];
    for (int i = 1; i < n; ++i) {
        int128 m1 = currentMod, r1 = currentRem;
        int128 m2 = moduli[i], r2 = remainders[i];
        int128 x, y;
        int128 g = exgcd(m1, m2, x, y);
        int128 diff = r2 - r1;
        if (diff % g != 0) { cout << "-1\n"; return 0; }

        int128 lcm = m1 / g * m2;
        x = (x * (diff / g)) % (m2 / g);
        if (x < 0) x += m2 / g;
        currentRem = (m1 * x + r1) % lcm;
        if (currentRem < 0) currentRem += lcm;
        currentMod = lcm;
    }

    long long result = (long long)(currentRem % currentMod);
    cout << result << '\n';
    return 0;
}