Data Structures

Segment Tree

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 100010;

int n, m;
vector<ll> arr;
vector<ll> tree;
vector<ll> lazy;

inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    
    int mid = (start + end) / 2;
    build(2 * node, start, mid);
    build(2 * node + 1, mid + 1, end);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

void updateRange(int node, int start, int end, int l, int r, ll val) {
    if (lazy[node] != 0) {
        tree[node] += (end - start + 1) * lazy[node];
        if (start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    
    if (start > end || start > r || end < l) return;
    
    if (start >= l && end <= r) {
        tree[node] += (end - start + 1) * val;
        if (start != end) {
            lazy[2 * node] += val;
            lazy[2 * node + 1] += val;
        }
        return;
    }
    
    int mid = (start + end) / 2;
    updateRange(2 * node, start, mid, l, r, val);
    updateRange(2 * node + 1, mid + 1, end, l, r, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

ll queryRange(int node, int start, int end, int l, int r) {
    if (start > end || start > r || end < l) return 0;
    
    if (lazy[node] != 0) {
        tree[node] += (end - start + 1) * lazy[node];
        if (start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    
    if (start >= l && end <= r) return tree[node];
    
    int mid = (start + end) / 2;
    ll p1 = queryRange(2 * node, start, mid, l, r);
    ll p2 = queryRange(2 * node + 1, mid + 1, end, l, r);
    return p1 + p2;
}

int main() {
    n = read(), m = read();
    arr.resize(n + 1);
    tree.resize(4 * n + 1);
    lazy.resize(4 * n + 1);
    
    for (int i = 1; i <= n; i++) {
        arr[i] = read();
    }
    
    build(1, 1, n);
    
    while (m--) {
        int op = read(), l = read(), r = read();
        if (op == 1) {
            ll val = read();
            updateRange(1, 1, n, l, r, val);
        } else {
            printf("%lld\n", queryRange(1, 1, n, l, r));
        }
    }
    
    return 0;
}
</ll></ll></ll></algorithm></vector></iostream>

Binary Indexed Tree (Fenwick Tree)

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const int MAXN = 500005;

int n, m;
vector<ll> nums;
vector<ll> bit;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int lowbit(int x) {
    return x & (-x);
}

void update(int index, ll delta) {
    while (index <= n) {
        bit[index] += delta;
        index += lowbit(index);
    }
}

ll query(int index) {
    ll sum = 0;
    while (index > 0) {
        sum += bit[index];
        index -= lowbit(index);
    }
    return sum;
}

int main() {
    n = read(), m = read();
    nums.resize(n + 1);
    bit.resize(n + 1);
    
    for (int i = 1; i <= n; i++) {
        nums[i] = read();
    }
    
    for (int i = 1; i <= m; i++) {
        int op = read();
        if (op == 1) {
            int l = read(), r = read(), val = read();
            update(l, val);
            if (r + 1 <= n) update(r + 1, -val);
        } else {
            int pos = read();
            printf("%lld\n", nums[pos] + query(pos));
        }
    }
    
    return 0;
}
</ll></ll></vector></iostream>

Priority Queue (Min-Heap)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;
const int MAXN = 100005;

int n;
vector<ll> heap;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void pushElement(ll value) {
    heap.push_back(value);
    int index = heap.size() - 1;
    
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[parent] <= heap[index]) break;
        swap(heap[parent], heap[index]);
        index = parent;
    }
}

void popElement() {
    if (heap.empty()) return;
    
    heap[0] = heap.back();
    heap.pop_back();
    
    int index = 0;
    int size = heap.size();
    
    while (true) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = index;
        
        if (left < size && heap[left] < heap[smallest])
            smallest = left;
        
        if (right < size && heap[right] < heap[smallest])
            smallest = right;
        
        if (smallest == index) break;
        
        swap(heap[index], heap[smallest]);
        index = smallest;
    }
}

ll getTop() {
    if (heap.empty()) return -1;
    return heap[0];
}

int main() {
    n = read();
    
    for (int i = 0; i < n; i++) {
        int op = read();
        if (op == 1) {
            ll x = read();
            pushElement(x);
        } else if (op == 2) {
            printf("%lld\n", getTop());
        } else {
            popElement();
        }
    }
    
    return 0;
}
</ll></vector></queue></iostream>

Monotonic Stack

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

typedef long long ll;
const int MAXN = 3000010;

int n;
vector<ll> input;
vector<ll> result;
stack<pair ll="">> st;

inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void computeNearestGreater() {
    for (int i = 0; i < n; i++) {
        while (!st.empty() && st.top().first <= input[i]) {
            st.pop();
        }
        
        if (st.empty()) {
            result[i] = -1;
        } else {
            result[i] = st.top().second;
        }
        
        st.push({input[i], i});
    }
}

int main() {
    n = read();
    input.resize(n);
    result.resize(n);
    
    for (int i = 0; i < n; i++) {
        input[i] = read();
    }
    
    computeNearestGreater();
    
    for (int i = 0; i < n; i++) {
        printf("%lld ", result[i]);
    }
    printf("\n");
    
    return 0;
}
</pair></ll></ll></stack></vector></iostream>

Monotonic Queue (Sliding Window Minimum)

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

typedef long long ll;
const int MAXN = 1000010;

int n, k;
vector<ll> arr;
vector<ll> minValues;
vector<ll> maxValues;
deque<pair ll="">> minDeque;
deque<pair ll="">> maxDeque;

inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void computeSlidingWindowExtremes() {
    for (int i = 0; i < n; i++) {
        // Compute minimum values
        while (!minDeque.empty() && minDeque.back().first >= arr[i]) {
            minDeque.pop_back();
        }
        
        minDeque.push_back({arr[i], i});
        
        while (minDeque.front().second <= i - k) {
            minDeque.pop_front();
        }
        
        if (i >= k - 1) {
            minValues.push_back(minDeque.front().first);
        }
        
        // Compute maximum values
        while (!maxDeque.empty() && maxDeque.back().first <= arr[i]) {
            maxDeque.pop_back();
        }
        
        maxDeque.push_back({arr[i], i});
        
        while (maxDeque.front().second <= i - k) {
            maxDeque.pop_front();
        }
        
        if (i >= k - 1) {
            maxValues.push_back(maxDeque.front().first);
        }
    }
}

int main() {
    n = read(), k = read();
    arr.resize(n);
    
    for (int i = 0; i < n; i++) {
        arr[i] = read();
    }
    
    computeSlidingWindowExtremes();
    
    for (ll val : minValues) {
        printf("%lld ", val);
    }
    printf("\n");
    
    for (ll val : maxValues) {
        printf("%lld ", val);
    }
    printf("\n");
    
    return 0;
}
</pair></pair></ll></ll></ll></vector></deque></iostream>

Disjoint Set Union (DSU)

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const int MAXN = 100010;

int n, m;
vector<int> parent;
vector<int> rank;
vector<int> size;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX == rootY) return;
    
    if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
        size[rootY] += size[rootX];
    } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
        size[rootX] += size[rootY];
    } else {
        parent[rootY] = rootX;
        rank[rootX]++;
        size[rootX] += size[rootY];
    }
}

int main() {
    n = read(), m = read();
    parent.resize(n + 1);
    rank.resize(n + 1, 0);
    size.resize(n + 1, 1);
    
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    while (m--) {
        int op = read(), x = read(), y = read();
        
        if (op == 1) {
            unionSets(x, y);
        } else {
            int rootX = find(x);
            int rootY = find(y);
            
            if (rootX == rootY) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
    }
    
    return 0;
}
</int></int></int></vector></iostream>

Sparse Table

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
const int MAXN = 1000010;
const int LOGN = 20;

int n, m;
vector<int> arr;
vector<vector>> st;
vector<int> logTable;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void buildSparseTable() {
    logTable.resize(n + 1);
    logTable[1] = 0;
    
    for (int i = 2; i <= n; i++) {
        logTable[i] = logTable[i / 2] + 1;
    }
    
    st.resize(n + 1, vector<int>(LOGN + 1));
    
    for (int i = 1; i <= n; i++) {
        st[i][0] = arr[i];
    }
    
    for (int j = 1; j <= LOGN; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int queryRange(int l, int r) {
    int j = logTable[r - l + 1];
    return max(st[l][j], st[r - (1 << j) + 1][j]);
}

int main() {
    n = read(), m = read();
    arr.resize(n + 1);
    
    for (int i = 1; i <= n; i++) {
        arr[i] = read();
    }
    
    buildSparseTable();
    
    while (m--) {
        int l = read(), r = read();
        printf("%d\n", queryRange(l, r));
    }
    
    return 0;
}
</int></int></vector></int></cmath></vector></iostream>

Graph Algorrithms

Dijkstra's Algorithm

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef long long ll;
const int MAXN = 100010;
const int MAXM = 200010;
const ll INF = 1e18;

int n, m, start;
vector<pair ll="">> adj[MAXN];
vector<ll> dist;
vector<bool> visited;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void dijkstra(int start) {
    dist.assign(n + 1, INF);
    visited.assign(n + 1, false);
    
    dist[start] = 0;
    priority_queue<pair int="">, vector<pair int="">>, greater<pair int="">>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        ll d = pq.top().first;
        pq.pop();
        
        if (visited[u]) continue;
        visited[u] = true;
        
        for (auto &edge : adj[u]) {
            int v = edge.first;
            ll weight = edge.second;
            
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    n = read(), m = read(), start = read();
    
    for (int i = 0; i < m; i++) {
        int u = read(), v = read();
        ll w = read();
        adj[u].push_back({v, w});
    }
    
    dijkstra(start);
    
    for (int i = 1; i <= n; i++) {
        if (dist[i] == INF) {
            printf("-1 ");
        } else {
            printf("%lld ", dist[i]);
        }
    }
    printf("\n");
    
    return 0;
}
</pair></pair></pair></bool></ll></pair></climits></queue></vector></iostream>

Kruskal's Algorithm for Minimum Spanning Tree

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 200010;

int n, m;
vector<int> parent;
vector<int> rank;
vector<pair int="" pair="">>> edges;
ll totalWeight;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    
    if (rootX == rootY) return;
    
    if (rank[rootX] < rank[rootY]) {
        parent[rootX] = rootY;
    } else if (rank[rootX] > rank[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootY] = rootX;
        rank[rootX]++;
    }
}

bool kruskal() {
    sort(edges.begin(), edges.end());
    
    for (auto &edge : edges) {
        int u = edge.second.first;
        int v = edge.second.second;
        ll weight = edge.first;
        
        if (find(u) != find(v)) {
            unionSets(u, v);
            totalWeight += weight;
        }
    }
    
    // Check if all nodes are connected
    int root = find(1);
    for (int i = 2; i <= n; i++) {
        if (find(i) != root) {
            return false;
        }
    }
    
    return true;
}

int main() {
    n = read(), m = read();
    parent.resize(n + 1);
    rank.resize(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    for (int i = 0; i < m; i++) {
        int u = read(), v = read();
        ll w = read();
        edges.push_back({w, {u, v}});
    }
    
    if (kruskal()) {
        printf("%lld\n", totalWeight);
    } else {
        printf("IMPOSSIBLE\n");
    }
    
    return 0;
}
</pair></int></int></algorithm></vector></iostream>

Dynamic Programming

0-1 Knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 1005;

int n, capacity;
vector<ll> weights;
vector<ll> values;
vector<vector>> dp;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void solveKnapsack() {
    dp.resize(n + 1, vector<ll>(capacity + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i] <= w) {
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i]] + values[i]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
}

int main() {
    n = read(), capacity = read();
    weights.resize(n + 1);
    values.resize(n + 1);
    
    for (int i = 1; i <= n; i++) {
        weights[i] = read();
    }
    
    for (int i = 1; i <= n; i++) {
        values[i] = read();
    }
    
    solveKnapsack();
    
    printf("%lld\n", dp[n][capacity]);
    
    return 0;
}
</ll></vector></ll></ll></algorithm></vector></iostream>

Unbounded Knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 1005;

int n, capacity;
vector<ll> weights;
vector<ll> values;
vector<ll> dp;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void solveUnboundedKnapsack() {
    dp.assign(capacity + 1, 0);
    
    for (int w = 1; w <= capacity; w++) {
        for (int i = 1; i <= n; i++) {
            if (weights[i] <= w) {
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
    }
}

int main() {
    n = read(), capacity = read();
    weights.resize(n + 1);
    values.resize(n + 1);
    
    for (int i = 1; i <= n; i++) {
        weights[i] = read();
    }
    
    for (int i = 1; i <= n; i++) {
        values[i] = read();
    }
    
    solveUnboundedKnapsack();
    
    printf("%lld\n", dp[capacity]);
    
    return 0;
}
</ll></ll></ll></algorithm></vector></iostream>

Complete Knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 1005;

int n, capacity;
vector<ll> weights;
vector<ll> values;
vector<ll> dp;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void solveCompleteKnapsack() {
    dp.assign(capacity + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        for (int w = weights[i]; w <= capacity; w++) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
}

int main() {
    n = read(), capacity = read();
    weights.resize(n + 1);
    values.resize(n + 1);
    
    for (int i = 1; i <= n; i++) {
        weights[i] = read();
    }
    
    for (int i = 1; i <= n; i++) {
        values[i] = read();
    }
    
    solveCompleteKnapsack();
    
    printf("%lld\n", dp[capacity]);
    
    return 0;
}
</ll></ll></ll></algorithm></vector></iostream>

Group Knapsack

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 1005;
const int MAXM = 105;

int n, capacity;
vector<int> groupSizes;
vector<vector>> groupWeights;
vector<vector>> groupValues;
vector<ll> dp;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void solveGroupKnapsack() {
    dp.assign(capacity + 1, 0);
    
    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= 0; w--) {
            for (int j = 0; j < groupSizes[i]; j++) {
                if (w >= groupWeights[i][j]) {
                    dp[w] = max(dp[w], dp[w - groupWeights[i][j]] + groupValues[i][j]);
                }
            }
        }
    }
}

int main() {
    n = read(), capacity = read();
    groupSizes.resize(n);
    groupWeights.resize(n);
    groupValues.resize(n);
    
    for (int i = 0; i < n; i++) {
        groupSizes[i] = read();
        groupWeights[i].resize(groupSizes[i]);
        groupValues[i].resize(groupSizes[i]);
        
        for (int j = 0; j < groupSizes[i]; j++) {
            groupWeights[i][j] = read();
        }
        
        for (int j = 0; j < groupSizes[i]; j++) {
            groupValues[i][j] = read();
        }
    }
    
    solveGroupKnapsack();
    
    printf("%lld\n", dp[capacity]);
    
    return 0;
}
</ll></vector></vector></int></algorithm></vector></iostream>

Mathematical Algorithms

Fast Exponentiation (Modular)

#include <iostream>
using namespace std;

typedef long long ll;

inline ll read() {
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

ll fastExponentiation(ll base, ll exponent, ll mod) {
    ll result = 1 % mod;
    
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        
        base = (base * base) % mod;
        exponent /= 2;
    }
    
    return result;
}

int main() {
    ll base = read();
    ll exponent = read();
    ll mod = read();
    
    ll result = fastExponentiation(base, exponent, mod);
    
    printf("%lld^%lld mod %lld = %lld\n", base, exponent, mod, result);
    
    return 0;
}
</iostream>

Sieve of Eratosthanes

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
const int MAXN = 10000005;

int n, m;
vector<bool> isPrime;
vector<int> primes;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void sieve() {
    isPrime.assign(MAXN, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i < MAXN; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < MAXN; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    for (int i = 2; i < MAXN; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
}

bool isPrimeNumber(int x) {
    if (x < 2) return false;
    
    for (int p : primes) {
        if (p * p > x) break;
        if (x % p == 0) return false;
    }
    
    return true;
}

int main() {
    n = read(), m = read();
    
    sieve();
    
    for (int i = 0; i < m; i++) {
        int x = read();
        if (isPrimeNumber(x)) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    
    return 0;
}
</int></bool></cmath></vector></iostream>

String Algorithms

KMP Algorithm

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const int MAXN = 1000010;

int n, m;
string text, pattern;
vector<int> lps;
vector<int> occurrences;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void computeLPS() {
    lps.resize(pattern.size());
    int len = 0;
    lps[0] = 0;
    
    for (int i = 1; i < pattern.size(); ) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void searchPattern() {
    int i = 0, j = 0;
    
    while (i < text.size()) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        
        if (j == pattern.size()) {
            occurrences.push_back(i - j);
            j = lps[j - 1];
        } else if (i < text.size() && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

int main() {
    cin >> text >> pattern;
    n = text.size();
    m = pattern.size();
    
    computeLPS();
    searchPattern();
    
    for (int pos : occurrences) {
        printf("%d\n", pos);
    }
    
    for (int i = 0; i < m; i++) {
        printf("%d ", lps[i]);
    }
    printf("\n");
    
    return 0;
}
</int></int></vector></iostream>

String Hashing

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

typedef long long ll;
const int MAXN = 1000010;
const ll BASE = 131;
const ll MOD = 1e9 + 7;

int n;
vector<string> strings;
unordered_map<ll int=""> hashCount;
vector<ll> powers;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

ll computeHash(const string &s) {
    ll hash = 0;
    for (char c : s) {
        hash = (hash * BASE + c) % MOD;
    }
    return hash;
}

void precomputePowers(int maxSize) {
    powers.resize(maxSize + 1);
    powers[0] = 1;
    
    for (int i = 1; i <= maxSize; i++) {
        powers[i] = (powers[i - 1] * BASE) % MOD;
    }
}

int main() {
    n = read();
    strings.resize(n);
    int maxSize = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> strings[i];
        if (strings[i].size() > maxSize) {
            maxSize = strings[i].size();
        }
    }
    
    precomputePowers(maxSize);
    
    int uniqueCount = 0;
    for (const string &s : strings) {
        ll h = computeHash(s);
        if (hashCount[h] == 0) {
            uniqueCount++;
        }
        hashCount[h]++;
    }
    
    printf("%d\n", uniqueCount);
    
    return 0;
}
</ll></ll></string></unordered_map></vector></iostream>