XCPC Template

发表于 更新于 阅读次数： 本文字数： 13k 阅读时长 ≈ 23 分钟

Template for XCPC

Discretization

1
2
3
4
5
6
7
8
9
10
11
std::vector<int> a(n + 1);
std::vector<int> c;
for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    c.push_back(a[i]);
}
std::sort(c.begin(), c.end());
int k = std::unique(c.begin(), c.end()) - c.begin();
for (int i = 1; i <= n; ++i) {
    a[i] = std::lower_bound(c.begin(), c.begin() + k, a[i]) - c.begin() + 1; // 1-indexed
}

Base_conversion

1
2
3
4
5
6
7
8
9
10
11
12
13
i64 x, base;
std::cin >> x >> base;
std::vector<int> res;
auto get = [&](auto self, i64 x) -> void {
    if (x / base > 0) {
        self(self, x / base);
    }
    res.push_back(x % base);
};
get(get, x);
for (int i = 0; i < res.size(); ++i) {
    std::cout << res[i] << ' ';
}

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
using i64 = long long;

constexpr i64 Mod = 998244353;
constexpr i64 N = 2e5 + 10;

std::vector<i64> fact(N + 1);
std::vector<i64> infact(N + 1);

i64 qpow(i64 a, i64 b, i64 mod) {
    i64 res = 1 % mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

i64 inv(i64 x) {
    return qpow(x, Mod - 2, Mod);
}

i64 C(int a, int b) {
    if (a < b || b < 0) return 0;
    return fact[a] * infact[b] % Mod * infact[a - b] % Mod;
}

void precalc() {
    fact[0] = 1;
    infact[0] = 1;
    for (int i = 1; i < N; ++i) {
        fact[i] = fact[i - 1] * i % Mod;
        infact[i] = infact[i - 1] * inv(i) % Mod;
    }
}

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
constexpr i64 INF = 1e18;

std::vector<std::vector<std::pair<int, i64>>> e(n + 1);
std::vector<i64> d(n + 1, INF);

auto dijkstra = [&](std::vector<std::vector<std::pair<int, i64>>>& e, std::vector<i64>& d, int s) -> void {
    std::vector<bool> vis(n + 1);
    d[s] = 0;
    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> q;
    q.push({0, s});
    while (q.size()) {
        auto [dist, u] = q.top();
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : e[u]) {
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push({d[v], v});
            }
        }
    }
};

DSU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct DSU {
    int n;
    std::vector<int> p;
    std::vector<int> sz;
    DSU(int n = 0) : n(n), p(n + 1, 0), sz(n + 1, 1) {
        std::iota(p.begin() + 1, p.end(), 1);
    }
    inline int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    bool same(int u, int v) {
        return find(u) == find(v);
    }
    bool merge(int u, int v) {
        int pu = find(u), pv = find(v);
        if (pu == pv) return false;
        sz[pu] += sz[pv];
        p[pv] = pu;
        return true;
    }
    int size(int x) {
        return sz[find(x)];
    }
};

Fenwick tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Fenwick {
    int n;
    std::vector<i64> c;
    Fenwick(int n = 0) : n(n), c(n + 1, 0) {}
    inline void add(int x, i64 t) {
        if (x == 0) return;
        for (; x <= n; x += x & -x) {
            c[x] += t;
        }
    }
    inline i64 sum(int x) {
        i64 res = 0;
        for (; x > 0; x -= x & -x) {
            res += c[x];
        }
        return res;
    }
};

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
struct KMP {
    std::vector<int> nxt;
    std::string s, t;
    int n, m;
    KMP(std::string a, std::string b) : s("?" + a), t("?" + b) {
        n = s.length() - 1, m = t.length() - 1;
        nxt.resize(m + 1);
        nxt[1] = 0;
        for (int i = 2; i <= m; ++i) {
            int j = i - 1;
            while (j != 0) {
                if (t[i] == t[nxt[j] + 1]) {
                    nxt[i] = nxt[j] + 1;
                    break;
                }
                j = nxt[j];
            }
        }
    }
    std::vector<int> get_start_pos(bool start_from_zero) {
        std::vector<int> res;
        for (int i = 1, j = 1; i <= n; ) {
            if (s[i] == t[j])
                ++i, ++j;
            else
                while (j != 1 && s[i] != t[j]) 
                    j = nxt[j - 1] + 1;
            if (j == 1 && s[i] != t[j])
                ++i;
            if (j == m + 1) {
                res.push_back((i - 1) - (j - 1) + 1 + (start_from_zero ? -1 : 0));
                j = nxt[m] + 1;
            }
        }
        return res;
    }
};

LCA (binary lifting)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
std::vector<std::vector<std::pair<i64, i64>>> e(n + 1);
for (i64 i = 1; i <= n - 1; ++i) {
    i64 u, v, w;
    std::cin >> u >> v >> w;
    e[u].push_back({v, w});
    e[v].push_back({u, w});
}
std::vector<i64> dis(n + 1);
std::vector<i64> dep(n + 1);
std::vector<std::vector<i64>> f(n + 1, std::vector<i64>(20));

auto dfs = [&](auto self, i64 u, i64 fa) -> void {
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for (int i = 1; (1 << i) <= dep[u]; ++i) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for (auto [v, w] : e[u]) {
        if (v == fa) continue;
        dis[v] = dis[u] + w;
        self(self, v, u);
    } 
    return;
};
dfs(dfs, 1, 0);

auto lca = [&](int u, int v) -> int { 
    if (dep[u] < dep[v]) std::swap(u, v);
    int temp = dep[u] - dep[v]; 
    for (int i = 0; (1 << i) <= temp; ++i) {
        if ((1 << i) & temp) {
            u = f[u][i]; 
        }
    }
    if (u == v) return u; 
    for (int i = (int)std::log2(n); i >= 0; --i) {
        if (f[u][i] != f[v][i]) {
            u = f[u][i]; 
            v = f[v][i]; 
        }
    }
    return f[u][0];   
};

Max flow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
struct Flow {
    static constexpr int INF = 1e9;
    int n;
    struct Edge {
        int to, cap;
        Edge(int to, int cap) : to(to), cap(cap) {}
    };
    std::vector<Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;
    Flow(int n) : n(n), g(n) {}
    bool bfs(int s, int t) {
        h.assign(n, -1);
        std::queue<int> que;
        h[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i : g[u]) {
                int v = e[i].to;
                int c = e[i].cap;
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t) return true;
                    que.push(v);
                }
            }
        }
        return false;
    }
    int dfs(int u, int t, int f) {
        if (u == t) return f;
        int r = f;
        for (int &i = cur[u]; i < int(g[u].size()); ++i) {
            int j = g[u][i];
            int v = e[j].to;
            int c = e[j].cap;
            if (c > 0 && h[v] == h[u] + 1) {
                int a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0) return f;
            }
        }
        return f - r;
    }
    void addEdge(int u, int v, int c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }
    int maxFlow(int s, int t) {
        int ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, INF);
        }
        return ans;
    }
};

Mono queue

1
2
3
4
5
6
7
8
9
10
11
std::vector<int> maxv_in_window_length_k_end_at_i(n + 1);
std::deque<int> q;
for (int i = 1; i <= n; ++i) {
    while(q.size() && q.back() < a[i]) q.pop_back();
    q.push_back(a[i]);
    if (i - k >= 1 && q.front() == a[i - k]) q.pop_front();
    if (i >= k) maxv_in_window_length_k_end_at_i[i] = q.front();
}
for (int i = k; i <= n; ++i) {
    std::cout << maxv_in_window_length_k_end_at_i[i] << ' ';
}

Mono stack

1
2
3
4
5
6
7
8
9
10
std::vector<int> l(n + 1, -1);
std::stack<int> s;
for (int i = 1; i <= n; ++i) {
    while (s.size() && s.top() <= a[i]) s.pop();
    if (s.size()) l[i] = s.top();
    s.push(a[i]);
}
for (int i = 1; i <= n; ++i) {
    std::cout << l[i] << ' ';
}

Seg merge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<std::array<int, 2>> seg(n);
for (int i = 0; i < n; i++) {
    int l, r;
    std::cin >> l >> r;
    seg[i] = {l, r};
}
std::sort(seg.begin(), seg.end());
std::vector<std::array<int, 2>> a;
for (auto [l, r] : seg) {
    if (!a.empty() && l <= a.back()[1]) {
        a.back()[1] = std::max(a.back()[1], r);
    }
    else {
        a.push_back({l, r});
    }
}

Segement tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
struct Info {
    int len; 
    i64 sum;
};

struct Tag {
    i64 add;
};

Info operator + (const Info& l, const Info& r) {
    return {l.len + r.len, l.sum + r.sum};
}

Info operator + (const Info& v, const Tag& t) {
    return {v.len, v.sum + t.add * v.len};
}

Tag operator + (const Tag& t1, const Tag& t2) {
    return {t1.add + t2.add};
}

struct Node {
    Tag t;
    Info val;
};

struct Segment_tree {
    int n;
    std::vector<Node> seg;
    std::vector<int> a;
    Segment_tree(int n) : n(n), seg(n * 4) {}
    void pushup(int id) {
        seg[id].val = seg[id << 1].val + seg[id << 1 | 1].val;
    }

    void settag(int id, Tag t) {
        seg[id].val = seg[id].val + t;
        seg[id].t = seg[id].t  + t;
    }

    void pushdown(int id) {
        if (seg[id].t.add != 0) {
            settag(id << 1, seg[id].t);
            settag(id << 1 | 1, seg[id].t);
            seg[id].t.add = 0;
        }
    }

    void init(std::vector<int>& b) {
        a = b;
    }

    void build(int id, int l, int r) {
        if (l == r) {
            seg[id].val = {1, a[l]};
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        pushup(id);
    }

    void modify(int id, int l, int r, int ql, int qr, Tag t) {
        if (l == ql && r == qr) {
            settag(id, t);
            return;
        }
        pushdown(id);
        int mid = l + r >> 1;
        if (qr <= mid) modify(id << 1, l, mid, ql, qr, t);
        else if (ql >= mid + 1) modify(id << 1 | 1, mid + 1, r, ql, qr, t);
        else modify(id << 1, l, mid, ql, mid, t), modify(id << 1 | 1, mid + 1, r, mid + 1, qr, t);
        pushup(id);
    }

    Info query(int id, int l, int r, int ql, int qr) {
        if (l == ql && r == qr) return seg[id].val;
        pushdown(id);
        int mid = l + r >> 1;
        if (qr <= mid) return query(id << 1, l, mid, ql, qr);
        else if (ql >= mid + 1) return query(id << 1 | 1, mid + 1, r, ql, qr);
        else return query(id << 1, l, mid, ql, mid) + query(id << 1 | 1, mid + 1, r, mid + 1, qr);
    }
};

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
constexpr i64 INF = 1e18;

std::vector<std::vector<std::pair<int, i64>>> e(n + 1);
std::vector<i64> d(n + 1, INF);

auto spfa = [&](std::vector<std::vector<std::pair<int, i64>>>& e, std::vector<i64>& d, int s) -> bool {
    std::vector<int> vis(n + 1, 0);
    std::vector<bool> st(n + 1, false);
    std::queue<int> q;
    q.push(s);
    d[s] = 0;
    ++vis[s];
    while (q.size()) {
        auto u = q.front();
        q.pop();
        st[u] = false;
        if (vis[u] > n) return true;
        for (auto [v, w] : e[u]) {
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                if (!st[v]) {
                    st[v] = true;
                    ++vis[v];
                    q.push(v);
                }
            }
        }
    }
    return false;
};

ST table

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct ST {
    int n;
    std::vector<std::vector<int>> fmin;
    std::vector<std::vector<int>> fmax;
    std::vector<int> Log2;
    ST(int n = 0) : n(n), fmin(n + 1, std::vector<int>(21)), fmax(n + 1, std::vector<int>(21)), Log2(n + 1, 0) {
        for (int i = 2; i <= n; ++i) {
            Log2[i] = Log2[i / 2] + 1;
        }
    }
    void init(std::vector<int>& a) {
        for (int i = 1; i <= n; ++i) {
            fmin[i][0] = a[i];
            fmax[i][0] = a[i];
        }
        for (int i = 1; i <= 20; ++i) {
            for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
                fmax[j][i] = std::max(fmax[j][i - 1], fmax[j + (1 << (i - 1))][i - 1]);
                fmin[j][i] = std::min(fmin[j][i - 1], fmin[j + (1 << (i - 1))][i - 1]);
            }
        }
    }
    int query_max(int l, int r) {
        int s = Log2[r - l + 1];
        return std::max(fmax[l][s], fmax[r - (1 << s) + 1][s]);
    }
    int query_min(int l, int r) {
        int s = Log2[r - l + 1];
        return std::min(fmin[l][s], fmin[r - (1 << s) + 1][s]);
    }
};

ST table (two dimension)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct ST_two_dimension {
    int n, m;
    std::vector<std::vector<std::vector<std::vector<int>>>> fmin;
    std::vector<std::vector<std::vector<std::vector<int>>>> fmax;
    std::vector<int> Log2;
    ST_two_dimension(int n = 0, int m = 0) : n(n), m(m), fmin(n + 1, std::vector<std::vector<std::vector<int>>>(m + 1, std::vector<std::vector<int>>(11, std::vector<int>(11)))), fmax(n + 1, std::vector<std::vector<std::vector<int>>>(m + 1, std::vector<std::vector<int>>(11, std::vector<int>(11)))), Log2(std::max(n, m) + 1, 0) {
        for (int i = 2; i <= std::max(n, m); ++i) {
            Log2[i] = Log2[i / 2] + 1;
        }
    }
    void init(std::vector<std::vector<int>>& a) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                fmin[i][j][0][0] = a[i][j];
                fmax[i][j][0][0] = a[i][j];  
            }
        }
        int t = Log2[n];
        for (int i = 0; i <= t; ++i) {
            for (int j = 0; j <= t; ++j) {
                if (i == 0 && j == 0) continue;
                for (int r = 1; r + (1 << i) - 1 <= n; ++r) {
                    for (int c = 1; c + (1 << j) - 1 <= m; ++c) {
                        if (i) {
                            fmin[r][c][i][j] = std::min(fmin[r][c][i - 1][j], fmin[r + (1 << (i - 1))][c][i - 1][j]);
                            fmax[r][c][i][j] = std::max(fmax[r][c][i - 1][j], fmax[r + (1 << (i - 1))][c][i - 1][j]);
                        }
                        else {
                            fmin[r][c][i][j] = std::min(fmin[r][c][i][j - 1], fmin[r][c + (1 << (j - 1))][i][j - 1]);
                            fmax[r][c][i][j] = std::max(fmax[r][c][i][j - 1], fmax[r][c + (1 << (j - 1))][i][j - 1]);
                        }
                    }
                }
            }
        }
    }
    int query_max(int x1, int y1, int x2, int y2) {
        int k1 = Log2[x2 - x1 + 1];
        int k2 = Log2[y2 - y1 + 1];
        int m1 = fmax[x1][y1][k1][k2];
        int m2 = fmax[x2 - (1 << k1) + 1][y1][k1][k2];
        int m3 = fmax[x1][y2 - (1 << k2) + 1][k1][k2];
        int m4 = fmax[x2 - (1 << k1) + 1][y2 - (1 << k2) + 1][k1][k2];
        return std::max({m1, m2, m3, m4});
    }
    int query_min(int x1, int y1, int x2, int y2) {
        int k1 = Log2[x2 - x1 + 1];
        int k2 = Log2[y2 - y1 + 1];
        int m1 = fmin[x1][y1][k1][k2];
        int m2 = fmin[x2 - (1 << k1) + 1][y1][k1][k2];
        int m3 = fmin[x1][y2 - (1 << k2) + 1][k1][k2];
        int m4 = fmin[x2 - (1 << k1) + 1][y2 - (1 << k2) + 1][k1][k2];
        return std::min({m1, m2, m3, m4});
    }
};