常见 OI 算法模板

Posted on 繁/简： set

天不遂人愿，事常逆己心。

无论如何，先继续向前走吧。


快速读入(数字) Fast Input

1
2
3
4
5
6
7
8
9
10
11
12
13
inline int read() {
    int s = 0, t = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')    t = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + ch - 48;
        ch = getchar();
    }
    return s * t;
}


字符串处理 String Processing

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
int n, m;
int fail[MAX_N];
int f[MAX_N], s[MAX_M];

// f: text    string
// s: pattern string

void getFail() {
    fail[0] = -1;
    for (int i = 2; i <= m; ++i) {
        int p = fail[i - 1];
        while (p != -1 && s[p + 1] != s[i])
            p = fail[p];
        fail[i] = p + 1;
    }
}

void match() {
    int j = 0;
    for (int i = 1; i <= n; ++i) {
        while (j != -1 && f[i] != s[j + 1])
            j = fail[j];
        ++j;
        if (j == m) {
            cout << i - m + 1 << endl;
            j = fail[j];
        }
    }
}

AC 自动机 AC Automaton

KMP + Trie。多模式串匹配算法。

后缀自动机 Suffix Automaton

处理字串 (尤其是后缀) 问题的强力数据结构。

最小表示法 Minimal Expression

字符串所有循环同构串中字典序最小的一个称为该字符串的最小表示法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string getCore(string str) {
    int i = 0, j = 1, k = 0;
    while (k < m && i < m && j < m) {
        char fir = str[(i + k) % m], sec = str[(j + k) % m];
        if (fir == sec) 
            ++k;
        else {
            (fir > sec) ? (i += (k + 1)) : (j += (k + 1));
            k = 0;
            if (i == j) ++j;
        }
    }
    i = min(i, j);
    string res = "";
    for (int k = 0; k < m; ++k) res += str[(i + k) % m];
    return res;
}


线段树 Segment Tree

带懒标记 (lazy tag) 维护区间和的线段树。支持：

  • 区间 \(+k\)
  • 区间求和
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
int n, m;
int a[MAX_N];
int tree[MAX_N << 2], tag[MAX_N << 2];

// a:    initial array
// tree: segment tree
// tag:  lazy tag

void add(int x, int l, int r, int k) {
    tag[x] += k;
    tree[x] += (r - l + 1) * k;
}

void pushdown(int x, int l, int r) {
    if (!tag[x])    return;
    int mid = (l + r) >> 1;
    add(x << 1, l, mid, tag[x]);
    add(x << 1 | 1, mid + 1, r, tag[x]);
    tag[x] = 0;
}

void build(int x, int l, int r) {
    if (l == r) {
        tree[x] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    tree[x] = tree[x << 1] + tree[x << 1 | 1];
}

void update(int x, int l, int r, int ql, int qr, int k) {
    if (ql <= l && r <= qr) {
        add(x, l, r, k);
        return;
    }
    int mid = (l + r) >> 1l;
    pushdown(x, l, r);
    if (ql <= mid)
        update(x << 1, l, mid, ql, qr, k);
    if (qr > mid)
        update(x << 1 | 1, mid + 1, r, ql, qr, k);
    tree[x] = tree[x << 1] + tree[x << 1 | 1];
}

int query(int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return tree[x];
    }
    int res = 0;
    int mid = (l + r) >> 1;
    pushdown(x, l, r);
    if (ql <= mid)
        res += query(x << 1, l, mid, ql, qr);
    if (qr > mid)
        res += query(x << 1 | 1, mid + 1, r, ql, qr);
    return res;
}


树状数组 Fenwick 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
int a[MAX_N];
int tree[MAX_N];

// a:    initial array
// tree: Fenwick tree 

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

void add(int x, int v) {
    while (x <= n) {
        tree[x] += v;
        x += lowbit(x);
    }
}

// query(x) returns dynamic prefix sum 1..x
int query(int x) {
    int res = 0;
    while (x) {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}


平衡搜索树 Balanced Search Tree

Splay

自平衡的伸展树。支持：

  • 插入 \(x\)
  • 删除 \(x\) (若有多个 \(x\)，仅删除一个)
  • 查询 \(x\) 的排名
  • 查询排名为 \(k\) 的数
  • 查询 \(x\) 的前驱
  • 查询 \(x\) 的后继
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
int root;
int cnt;

int ch[MAX_N][2];
int fa[MAX_N];
int val[MAX_N];
int tot[MAX_N];
int size[MAX_N];

// root: root of splay tree

// ch:   child links, 0 for left, 1 for right
// fa:   parent links
// val:  value property
// tot:  # of val
// size: size of the subtree

inline int check(int x) {
    return ch[fa[x]][1] == x;	
}

inline void update(int x) {
    size[x] = size[ch[x][0]] + size[ch[x][1]] + tot[x];	
}

inline void rotate(int x) {
    int k = check(x), y = fa[x], u = fa[y], d = ch[x][k ^ 1];
    ch[y][k] = d, fa[d] = y;
    ch[u][check(y)] = x, fa[x] = u;
    ch[x][k ^ 1] = y, fa[y] = x;
    update(x), update(y);
}

inline void splay(int x, int to) {
    while (fa[x] != to) {
        int y = fa[x], u = fa[y];
        if (u != to) {
            if (check(x) == check(y))	rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
    if (!to)	root = x;
}

inline void insert(int x) {
    int cur = root, f = 0;
    while (cur && val[cur] != x) 
        f = cur, cur = ch[cur][x > val[cur]];
    if (cur)	++tot[cur];
    else {
        cur = ++cnt;
        if (f)	ch[f][x > val[f]] = cur;
        size[cur] = tot[cur] = 1, val[cur] = x, fa[cur] = f;
        ch[cur][0] = ch[cur][1] = 0;
    }
    splay(cur, 0);
}

inline void find(int x) {
    int cur = root;
    while (ch[cur][x > val[cur]] && val[cur] != x)	
        cur = ch[cur][x > val[cur]];
    splay(cur, 0);
}

inline int kth(int k) {
    int cur = root;
    while (1) {
        if (ch[cur][0] && k <= size[ch[cur][0]])	
            cur = ch[cur][0];
        else if (size[ch[cur][0]] + tot[cur] < k)	
            k -= size[ch[cur][0]] + tot[cur], cur = ch[cur][1];
        else return cur;
    }
}

inline int pre(int x) {
    find(x);
    if (val[root] < x)	
        return root;
    int cur = ch[root][0];
    while (ch[cur][1])	
        cur = ch[cur][1];
    return cur;	
}

inline int nxt(int x) {
    find(x);
    if (val[root] > x)	
        return root;
    int cur = ch[root][1];
    while (ch[cur][0])	
        cur = ch[cur][0];
    return cur;	
}

inline void remove(int x) {
    int bef = pre(x), aft = nxt(x);
    splay(bef, 0), splay(aft, bef);
    int del = ch[aft][0];
    if (tot[del] > 1)	 
        --tot[del], splay(del, 0);
    else 
        ch[aft][0] = tot[del] = val[del] = 0;
}

int main() {
    
    insert(0x3f3f3f3f);
    insert(0xcfcfcfcf);
    
    while (tt--) {
        cin >> opt;
        cin >> x;
        switch (opt) {
            case 1: insert(x); break;
            case 2: remove(x); break;
            case 3: find(x), printf("%d\n", size[ch[root][0]]); break;	
            case 4: printf("%d\n", val[kth(x + 1)]); break;
            case 5: printf("%d\n", val[pre(x)]); break;
            case 6: printf("%d\n", val[nxt(x)]); break;
        }	
    }

    return 0;
}

Treap

BST Tree + Heap。这里的模板是非旋转的 FHQ Treap 版本。


最短路算法 Shortest Path

Dijkstra

堆优化的单源最短路算法。复杂度 \(O((n+m)\log{n})\)，无法处理负权边。

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
int head[MAX_N];
int to[MAX_N];
int val[MAX_N];
int nxt[MAX_N];

int dis[MAX_N];

// head, to, val, nxt: adjacency list
// dis: shortest distance

struct Node {
    int x, d;
    
    Node(int _x, int _d) : x(_x), d(_d) {}
    
    bool operator < (const node& that) const {
        return d > that.d;    // pq is default maximum
    }
};

priority_queue<node> pq;

void addEdge(int x, int y, int v) {
    to[++cnt] = y;
    val[cnt] = v;
    next[cnt] = head[x];
    head[x] = cnt;
}

void dijkstra(int s) {
    for (int i = 1; i <= n; ++i)
        dis[i] = inf;
    dis[s] = 0;
    pq.push(Node(s, 0));
    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        int x = cur.x, d = cur.d;
        if (d != dis[x])    continue;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = to[i];
            if (dis[x] + val[i] < dis[y]) {
                dis[y] = dis[x] + val[i];
                pq.push(Node(y, dis[y]));
            }
        }
    }
}

SPFA

队列优化的 Bellman-Ford-Moore 的单源最短路算法，最坏复杂度 \(O(nm)\)，可以处理负权边。

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
31
int dis[MAX_N];
int cnt[MAX_N];
bool vis[MAX_N];

queue<int> q;

bool spfa(int s) {
    for (int i = 1; i <= n; ++i)    dis[i] = inf;
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = to[i];
            if (dis[x] + val[i] < dis[y]) {    // relaxation
                dis[y] = dis[x] + val[i];
                cnt[y] = cnt[x] + 1;
                if (cnt[y] >= n)
                    return false;    // negative weight cycle exists
                if (!vis[y]) {
                    q.push(y);
                    vis[y] = 1; 
                }
            }
        }
    }
    return true;
}

Floyd

能求出任意点对间的最短路，复杂度 \(O(n^3)\)。能处理负权边。

1
2
3
4
5
6
7
for (int k = 1; k <= n; ++k) {
    for (int x = 1; x <= n; ++x) {
        for (int y = 1; y <= n; ++y) {
            f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
        }
    }
}


最小生成树 Minimum Spanning Tree

Kruskal

基于贪心的最小生成树算法，复杂度 \(O(m\log{m})\)。

将边按权从小到大排序，依次加入初始为空的生成树。若某次加边产生了环 (用并查集维护连通块关系)，就舍弃这条边，直到成功加入了 \(n-1\) 条边。

Prim

与 Kruskal 不同，Prim 维护的是点集而不是边集。复杂度 \(O((n+m)\log{n})\)。

每次选择离点集最近的点更新距离，并将其加入点集。


最近公共祖先 Lowest Common Ancestor

倍增求 LCA。预处理复杂度 \(O(n\log{n})\)，单次查询复杂度 \(O(\log{n})\)。

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
int fa[MAX_N][15];
int dep[MAX_N];

// fa[x][i]: from x to its 2^i ancestor
// dep     : depth

void dfs(int u, int f) {
    fa[u][0] = f;
    dep[u] = dep[f] + 1;

    for (int i = 1; i < 13; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int to : e[u]) {
        if (to == f)    continue;
        dfs(to, u);    
    }
}

int LCA(int x, int y) {
    if (dep[x] < dep[y])    swap(x, y);

    int gap = dep[x] - dep[y];
    for (int i = 0; i < 13; ++i) {
        if (!gap)   break;
        if (gap & 1)    x = fa[x][i];
        gap >>= 1;
    }
    if (x == y) return x;
    for (int i = 12; i >= 0; --i) {
        if (fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}


计算几何 Computational Geometry

凸包 Convex Hull

Andrew 算法求凸包，使用单调栈分开求上下凸壳，避免了 Graham 算法的精度问题。复杂度 \(O(n\log{n})\)。

该模板将输出凸包上所有的点。

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
struct Point {
    int id;
    int x, y;

    bool operator < (const Point& p) {
        if (x == p.x)   return y < p.y;
        return x < p.x;
    }

    Point operator - (const Point& p) const { 
        return {0, x - p.x, y - p.y};
    }
} p[MAX_N];

Point sta[MAX_N];
int top;

int cross(Point p1, Point p2) {
    return p1.x * p2.y - p1.y * p2.x; 
}

void andrew() {
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; ++i) {
        while (top > 1 && cross(p[i] - sta[top - 1], sta[top] - sta[top - 1]) > 0) {
            --top;
        }
        sta[++top] = p[i];
    }    
    if (top < n) {
        int tmp = top;
        for (int i = n - 1; i > 0; --i) {
            while (top > tmp && cross(p[i] - sta[top - 1], sta[top] - sta[top - 1]) > 0)
                --top;
            sta[++top] = p[i];
        }
        if (n > 1) --top;
    }
    for (int i = 1; i <= top; ++i)  cout << sta[i].id << endl;
}


数论 Number Theory

扩展欧几里得算法 Extended Euclidean Algorithm

对于方程 \(ax+by=d\)，其中 \(d=\gcd(a,b)\)，扩欧能够求出该方程的一组可行解。

1
2
3
4
5
6
7
8
9
10
11
12
int Exgcd(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    int d = Exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}

对于方程 \(ax+by=c \ \ (d|c)\)，我们先用扩欧求出 \(ax+by=d\) 的一组解 \(x',y'\)。令 \(T=\frac{b}{d}\)，原方程 \(x\) 的最小正整数解为 \(x_1=\frac{c}{d}x'\mod{T}\).

欧拉筛 Euler's Sieve

欧拉筛线性筛质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> prime;
bool not_prime[MAX_N];

void Sieve() {
    for (int i = 2; i <= n; ++i) {
        if (!not_prime[i])
            prime.push_back(i);
        for (int x : prime) {
            if (i * x > n)    break;
            not_prime[i * x] = true;
            if (i % x == 0)    break;
        }
    }
}

欧拉函数 Euler's Totient

\(\varphi(n)\) 表示的是小于等于 \(n\) 与 \(n\) 互质的数的个数。当 \(n\) 为质数时显然有 \(\varphi(n)=n-1\)。

筛法求欧拉函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> prime;
bool not_prime[MAX_N];
int phi[MAX_N];

void Sieve() {
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!not_prime[i]) {
            prime.push_back(i);
            phi[i] = i - 1;
        }
        for (int x : prime) {
            if (i * x > n)    break;
            not_prime[i * x] = true;
            if (i % x == 0) {
                phi[i * x] = phi[i] * x;
                break;
            }
            phi[i * x] = phi[i] * (x - 1);
        }
    }
}


杂项 Miscellaneous

STL::set

set 与 multiset 的用法。

  • insert(const g)
  • erase(const g/iterator pos)
  • count(const g) 在 set 中只有 0/1 两种结果
  • find(const g) 返回 iterator，若没找到返回 end()
  • lower_bound(const g)
  • upper_bound(const g)

STL::bitset

bitset 的用法。定义 bitset<10000> (长度为 10000 的 bitset)。

  • count() 返回 true 的数量
  • set(pos, val = true/false)
  • set() [无参数] 将 bitset 重置为 true
  • reset(pos) 相当于 set(pos, val = false)
  • reset() [无参数] 将 bitset 重置为 false
  • flip(pos)
  • flip() [无参数] 翻转每一位
  • operators [], ==/!=, &/&=, |/|=, ^/^=, ~, <</<<=, >>/>>=.

离散化 Discretization

很经典的 technique，能够有效缩小 data scale。复杂度 \(O(n\log{n})\)。

1
2
3
4
5
for (int i = 1; i <= n; ++i)    t[i] = a[i];
sort(t + 1, t + n + 1);
int len = unique(t + 1, t + n + 1) - (t + 1);
for (int i = 1; i <= n; ++i)
    a[i] = lower_bound(t + 1, t + len + 1, a[i]) - t;
-----------------------------------そして、次の曲が始まるのです。-----------------------------------