【福利】洛谷模板汇总

Posted on Symbols count in article: 11k Reading time ≈ 39 mins.

Graph Theory

Disjoint Set

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
#include <iostream>
#define MAX_N 10000
using namespace std;
int n, m, f, x, y, father[MAX_N+5];
int getfather(int v) {
    if (father[v] == v) {
        return v;
    }
    father[v] = getfather(father[v]);
    return father[v];
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
    for (int i = 0; i < m; i++) {
        cin >> f >> x >> y;
        if (f == 1) {
            int f1 = getfather(x);
            int f2 = getfather(y);
            if (f1 != f2) {
                father[f1] = f2;
            }
        } else {
            int f1 = getfather(x);
            int f2 = getfather(y);
            if (f1 != f2) {
                cout << "N" << endl;
            } else {
                cout << "Y" << endl;
            }
        }
    }
    return 0;
}

Minimum Spanning Tree

Kruskal

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 5000
#define MAX_M 200000
using namespace std;
struct node {
    int u, v, l;
} edge[MAX_M+5];
int n, m, tot = 0;
int father[MAX_N+5];
bool comp(const node &a, const node &b) {
    return a.l < b.l;
}
int getfather(int v) {
    if (father[v] == v) {
        return v;
    }
    father[v] = getfather(father[v]);
    return father[v];
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].l;
    }
    sort(edge, edge+m, comp);
    for (int i = 1; i <= n; i++)	father[i] = i;
    int flag = n-1;
    for (int i = 0; i < m; i++) {
        int f1 = getfather(edge[i].u);
        int f2 = getfather(edge[i].v);
        if (f1 != f2) {
            father[f1] = f2;
            tot += edge[i].l;
            flag--;
        }
        if (flag == 0)	break;
    }
    if (flag == 0) {
        cout << tot;
    } else {
        cout << "orz";
    }
    return 0;
}

Prim

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
#include <bits/stdc++.h>
#define MAX_N 5000
#define INF 2147483647
using namespace std;
vector <int> G[MAX_N+5], E[MAX_N+5];
int n, m, dis[MAX_N+5], tot;    bool col[MAX_N+5];
void addedge(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c);}
void Prim() {
    for (int i = 1; i <= n; i++) dis[i] = INF;	dis[1] = 0;
    for (int i = 1, u = -1; i <= n; i++, u = -1) {
        for (int j = 1; j <= n; j++)
            if (!col[j] && (u == -1 || dis[u] > dis[j]))	u = j;
        col[u] = true, tot += dis[u];
        for (int j = 0; j < (int)G[u].size(); j++) {
            int v = G[u][j], c = E[u][j];
            if (!col[v] && dis[v] > c)	dis[v] = c;
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, u, v, c; i < m; i++)
        scanf("%d%d%d", &u, &v, &c), addedge(u, v, c), addedge(v, u, c);
    Prim();	printf("%d", tot);
    return 0;
}

Shortest Path

Dijkstra

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
#include <bits/stdc++.h>
#define MAX_N 10000
#define INF 2147483647
#define pii pair <int, int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
int n, m, s, dis[MAX_N+5];
vector <int> G[MAX_N+5], E[MAX_N+5];
void addedge(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c);}
void Dijkstra() {
    for (int i = 1; i <= n; i++)	dis[i] = INF;	dis[s] = 0;
    priority_queue <pii> que;	que.push(mp(0, s));
    while (!que.empty()) {
        int u = que.top().sec, d = que.top().fir;
        que.pop();	if (dis[u] != -d)	continue;
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i], c = E[u][i];
            if (dis[u]+c >= dis[v])	continue;
            dis[v] = dis[u]+c, que.push(mp(-dis[v], v));
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0, u, v, c; i < m; i++)
        scanf("%d%d%d", &u, &v, &c), addedge(u, v, c);
    Dijkstra();
    for (int i = 1; i <= n; i++)	printf("%d ", dis[i]);
    return 0;
}

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
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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_M 500000
#define MAX_N 10000
#define INF 2147483647
using namespace std;
struct node {
    int v, len, next;
    node() {
        v = len = next = 0;
    }
} edge[MAX_M+5];
int n, m, s;
int first[MAX_N+5], cnt = 0;
int dis[MAX_N+5];
void insert(int u, int v, int l) {
    cnt++;
    edge[cnt].v = v;
    edge[cnt].len = l;
    edge[cnt].next = first[u];
    first[u] = cnt;
}
void SPFA() {
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
    }
    int que[MAX_N*20+5], mark[MAX_N+5];
    int head = 0, tail = 1;
    memset(mark, 0, sizeof(mark));
    que[1] = s;
    mark[s] = 1;
    dis[s] = 0;
    while (head <= tail) {
        head++;
        for (int tmp = first[que[head]]; tmp; tmp = edge[tmp].next) {
            if (dis[que[head]]+edge[tmp].len < dis[edge[tmp].v]) {
                dis[edge[tmp].v] = dis[que[head]]+edge[tmp].len;
                if (mark[edge[tmp].v] == 0) {
                    mark[edge[tmp].v] = 1;
                    tail++;
                    que[tail] = edge[tmp].v;
                }
            }
        }
        mark[que[head]] = 0;
    }
}
int main() {
    cin >> n >> m >> s;
    memset(first, 0, sizeof(first));
    int u, v, l;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> l;
        insert(u, v, l);
    }
    SPFA();
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    return 0;
}

Tarjan

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define MAX_N 100000
using namespace std;
int n, m, c[MAX_N+5], f[MAX_N+5];
int dfn[MAX_N+5], low[MAX_N+5], col[MAX_N+5], val[MAX_N+5], ind, cnt;
vector <int> G[MAX_N+5], E[MAX_N+5];
stack <int> sta;
bool insta[MAX_N+5];
void tarjan(int u) {
    dfn[u] = low[u] = ++ind, sta.push(u), insta[u] = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!dfn[v])	tarjan(v), low[u] = min(low[u], low[v]);
        else if (insta[v])	low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        cnt++;
        for (int i = sta.top(); ; i = sta.top()) {
            col[i] = cnt, val[cnt] += c[i], insta[i] = false;
            sta.pop();	if (u == i)	break;
        }
    }
}
int DFS(int u) {
    if (f[u])	return f[u];
    int mx = 0;
    for (int i = 0; i < E[u].size(); i++)	mx = max(mx, DFS(E[u][i]));
    return f[u] = val[u]+mx;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	scanf("%d", &c[i]);
    while (m--) {
        int u, v;	scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])	tarjan(i);
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];	if (col[u] == col[v])	continue;
            E[col[u]].push_back(col[v]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= cnt; i++)
        if (!f[i])	ans = max(ans, DFS(i));
    printf("%d", ans);
    return 0;
}

Cut-Vertex

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
#include <iostream>
#include <cstdio>
#define MAX_N 100000
#define MAX_M 200000
using namespace std;
struct Edge {
    int v, next;
} edge[MAX_M+5];
int first[MAX_N+5], flag[MAX_N+5], num[MAX_N+5], low[MAX_N+5];
int n, m, cnt = 0;
void insert(int u, int v, int pos) {
    edge[pos].next = first[u];
    edge[pos].v = v;
    first[u] = pos;
}
void dfs(int cur, int father) {
    int child = 0;
    num[cur] = low[cur] = ++cnt;
    for (int tmp = first[cur]; tmp; tmp = edge[tmp].next) {
        if (!num[edge[tmp].v]) {
            child++;
            dfs(edge[tmp].v, cur);
            low[cur] = min(low[cur], low[edge[tmp].v]);
            if (low[edge[tmp].v] >= num[cur]) {
                flag[cur] = 1;
            }
        } else if (num[edge[tmp].v] < num[cur] && edge[tmp].v != father) {
            low[cur] = min(low[cur], num[edge[tmp].v]);
        }
    }
    if (father == -1 && child == 1) {
        flag[cur] = 0;
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        insert(u, v, i*2+1);
        insert(v, u, i*2+2);
    }
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        if (!num[i]) {
            dfs(i, -1);
        }
        if (flag[i]) {
            tot++;
        }
    }
    cout << tot << endl;
    for (int i = 1; i <= n; i++) {
        if (flag[i]) {
            cout << i << " ";
        }
    }
    return 0;
}

Lowest Common Ancestor

Doubling

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
#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 500000
using namespace std;
struct Edge {
    int next, to;
} edge[(MAX_N<<1)+5];
int n, m, s, x, y, cnt;
int d[MAX_N+5], p[MAX_N+5][25], first[MAX_N+5];
bool vis[MAX_N+5];
inline int read() {
    int ret = 0;	char ch = getchar();
    while (ch < '0' || ch > '9')	ch = getchar();
    while (ch >= '0' && ch <= '9')	ret = ret*10+ch-'0', ch = getchar();
    return ret;
}
void INSERT(int a, int b) {
    edge[++cnt].next = first[a];
    edge[cnt].to = b;
    first[a] = cnt;
}
void DFS(int u) {
    vis[u] = true;
    for (int i = 1; (1<<i) <= n; i++) {
        if ((1<<i) <= d[u]) {
            p[u][i] = p[p[u][i-1]][i-1];
        }
    }
    for (int i = first[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (!vis[v]) {
            d[v] = d[u]+1;
            p[v][0] = u;
            DFS(v);
        }
    }
}
int LCA(int a, int b) {
    int i, j;
    if (d[a] < d[b])	swap(a, b);
    for (i = 0; (1<<i) <= d[a]; i++) {}
    i--;
    for (j = i; j >= 0; j--) {
        if (d[a]-(1<<j) >= d[b]) {
            a = p[a][j];
        }
    }
    if (a == b) {
        return a;
    }
    for (j = i; j >= 0; j--) {
        if (p[a][j] != p[b][j]) {
            a = p[a][j];
            b = p[b][j];
        }
    }
    return p[a][0];
}
int main() {
    n = read(), m = read(), s = read();
    for (int i = 1; i < n; i++) {
        x = read(), y = read();
        INSERT(x, y);
        INSERT(y, x);
    }
    DFS(s);
    for (int i = 0; i < m; i++) {
        x = read(), y = read();
        cout << LCA(x, y) << endl; 
    }
    return 0;
}

Heavy Path Decomposition

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
#include <bits/stdc++.h>
#define MAX_N 500000
using namespace std;
vector <int> G[MAX_N+5];
int n, m, r, dep[MAX_N+5], sz[MAX_N+5];
int fa[MAX_N+5], son[MAX_N+5], top[MAX_N+5];
void DFS(int u) {
    sz[u] = 1;
    for (auto v : G[u]) {
        if (v == fa[u])	continue;
        fa[v] = u, dep[v] = dep[u]+1, DFS(v), sz[u] += sz[v];
        if (!son[u] || sz[son[u]] < sz[v])	son[u] = v;
    }
}
void DFS(int u, int tp) {
    top[u] = tp;	if (son[u])	DFS(son[u], tp);
    for (auto v : G[u])	if ((v^fa[u]) && (v^son[u]))	DFS(v, v);
}
int LCA(int u, int v) {
    while (top[u]^top[v])
        if (dep[top[u]] > dep[top[v]])	u = fa[top[u]];
        else	v = fa[top[v]];
    return dep[u] < dep[v] ? u : v;
}
int main() {
    scanf("%d%d%d", &n, &m, &r);	for (int i = 1, u, v; i < n; i++) scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
    DFS(r), DFS(r, r);	while (m--) {int u, v;	scanf("%d%d", &u, &v);	printf("%d\n", LCA(u, v));}	return 0;
}

Negative Loop

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 200000
#define SIZE 25000000
using namespace std;
int f;    char BUF[SIZE], *buf = BUF;
inline void read(int &x) {
    bool flag = 0;	while (*buf < 48)	if (*buf++ == 45)	flag = 1;
    x = 0;	while (*buf > 32)	x = x*10+*buf++-48;	x = flag ? -x : x;
}
vector <int> G[MAX_N+5], E[MAX_N+5];
int dis[MAX_N+5];
bool insta[MAX_N+5], flag;
void init(int n) {
    flag = false;
    for (int i = 1; i <= n; i++)	G[i].clear(), E[i].clear();
    memset(dis, 0, sizeof(dis)), memset(insta, false, sizeof(insta));
}
void DFS(int u) {
    insta[u] = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i], c = E[u][i];
        if (dis[u]+c >= dis[v])	continue;
        if (insta[v] || flag) {flag = true;	break;}
        dis[v] = dis[u]+c, DFS(v);
    }
    insta[u] = false;
}
int main() {
    f = fread(BUF, 1, SIZE, stdin);
    int T;	read(T);
    while (T--) {
        int n, m;	read(n), read(m);	init(n);
        while (m--) {
            int u, v, c;	read(u), read(v), read(c);
            G[u].push_back(v), E[u].push_back(c);
            if (c >= 0)	G[v].push_back(u), E[v].push_back(c);
        }
        for (int i = 1; i <= n; i++) {DFS(i);	if (flag)	break;}
        if (flag)	printf("YE5\n");
        else	printf("N0\n");
    }
    return 0;
}

Network 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
#include <bits/stdc++.h>
#define MAX_N 10000
#define MAX_M 100000
#define INF 0x7f7f7f7f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[(MAX_M<<1)+5];
void init() {memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que;	que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow;	int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = 1; i <= n; i++) cr[i] = pr[i];}
void rec() {for (int i = 1; i <= n; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0;    cpy();	while (BFS()) ret += DFS(s, INF), rec();	return ret;}
int main() {
    read(n), read(m), read(s), read(t), init();
    for (int i = 1, u, v, c; i <= m; i++)
        read(u), read(v), read(c), addedge(u, v, c);
    return printf("%d\n", Dinic()), 0;
}

Minimum Cost Maximum 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
#include <bits/stdc++.h>
#define MAX_N 5000
#define MAX_M 50000
#define INF 0x7f7f7f7f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[(MAX_M<<1)+5];
void init() {memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t]*flow;	return true;
}
int main() {
    read(n), read(m), read(s), read(t), init();
    for (int i = 1, u, v, c, w; i <= m; i++)
        read(u), read(v), read(c), read(w), addedge(u, v, c, w);
    while (SPFA()) ;	printf("%d %d\n", mxf, mic);
    return 0;
}

Bipartite Matching

Hungary

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 1000
using namespace std;
int n, m, e, match[MAX_N+5], cnt;
vector <int> G[MAX_N+5];
bool vis[MAX_N+5];
bool DFS(int u) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) {
            vis[v] = true;
            if (!match[v] || DFS(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}
int main() {
    cin >> n >> m >> e;
    int a, b;
    for (int i = 0; i < e; i++) {
        cin >> a >> b;
        if (a > n || b > m)	continue;
        G[a].push_back(b);
    }
    for (int i = 1; i <= n; i++) {
        memset(vis, false, sizeof(vis));
        if (DFS(i)) {
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

Dinic

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 2000
#define MAX_M 1000000
#define INF 2147483647
using namespace std;
int n, m, s, t, n1, n2;
int pre[MAX_N+5], tmp[MAX_N+5], d[MAX_N+5], cnt;
struct node {int v, c, nxt;} E[MAX_M*2+MAX_N*2+5];
void init() {cnt = 0; s = 0, t = n; memset(pre, -1, sizeof(pre));}
void insert(int u, int v, int c) {E[cnt].v = v, E[cnt].c = c, E[cnt].nxt = pre[u], pre[u] = cnt++;}
bool BFS() {
    memset(d, -1, sizeof(d));
    queue <int> que;
    que.push(s), d[s] = 0;
    while (!que.empty()) {
        int u = que.front();
        for (int i = pre[u]; i != -1; i = E[i].nxt) {
            int v = E[i].v;
            if (E[i].c && d[v] == -1) {
                d[v] = d[u]+1;
                que.push(v);
            }
        }
        que.pop();
    }
    return d[t] != -1;
}
int DFS(int u, int flow) {
    if (u == t)	return flow;
    int ret = 0;
    for (int &i = pre[u]; i != -1; i = E[i].nxt) {
        int v = E[i].v;
        if (E[i].c && d[u]+1 == d[v]) {
            int tmp = DFS(v, min(flow, E[i].c));
            E[i].c -= tmp, E[i^1].c += tmp, flow -= tmp, ret += tmp;
            if (!flow)	break;
        }
    }
    if (!ret)	d[u] = -1;
    return ret;
}
int Dinic() {
    int ret = 0;
    for (int i = 0; i <= n; i++)	tmp[i] = pre[i];
    while (BFS()) {
        ret += DFS(s, INF);
        for (int i = 0; i <= n; i++)	pre[i] = tmp[i];
    }
    return ret;
}
int main() {
    scanf("%d%d%d", &n1, &n2, &m);	n = n1+n2+1;
    init();
    for (int i = 1; i <= n1; i++)	insert(s, i, 1), insert(i, s, 0);
    for (int i = n1+1; i <= n1+n2; i++)	insert(i, t, 1), insert(t, i, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (u > n1 || v > n2)	continue;
        insert(u, n1+v, 1), insert(n1+v, u, 0);
    }
    printf("%d", Dinic());
    return 0;
}

Math

Gaussian Elimination

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
#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 100
#define EXP 1e-7
using namespace std;
typedef double fnt;
int n;    vector <fnt> f[MAX_N+5];	fnt ans[MAX_N+5];
bool gauss() {
    for (int i = 1, tmp; i <= n; i++) {
        for (tmp = i; tmp <= n; tmp++)	if (f[tmp][i] <= -EXP || f[tmp][i] >= EXP)	break;
        if (tmp > n)	return false;	swap(f[i], f[tmp]);
        for (int j = 1; j <= n; j++) {
            fnt div = f[j][i]/f[i][i];	if (j == i)	continue;
            for (int k = i; k <= n+1; k++)	f[j][k] -= f[i][k]*div;
        }
    }
    for (int i = 1; i <= n; i++)	ans[i] = f[i][n+1]/f[i][i];
    return true;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        f[i].push_back(0);
        for (int j = 1; j <= n+1; j++) {
            fnt x;	scanf("%lf", &x);
            f[i].push_back(x);
        }
    }
    if (gauss())	for (int i = 1; i <= n; i++)	printf("%.2lf\n", ans[i]);
    else	printf("No Solution");
    return 0;
}

Inverse

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <cstdio>
#define MAX_N 3000000
using namespace std;
typedef long long lnt;
lnt inv[MAX_N+5];
void init(int n, lnt p) {inv[0] = inv[1] = 1;    for (int i = 2; i <= n; i++)	inv[i] = (p-p/i*inv[p%i]%p)%p;}
int main() {
    int n;	lnt p;	scanf("%d%lld", &n, &p);
    init(n, p);
    for (int i = 1; i <= n; i++)	printf("%lld\n", inv[i]);
    return 0;
}

Linear Basis

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#define MAX_N 50
using namespace std;
typedef long long lnt;
int n;    lnt base[MAX_N+5], pow[MAX_N+5];
int main() {
    scanf("%d", &n);	pow[0] = 1;
    for (int i = 1; i <= MAX_N; i++)	pow[i] = pow[i-1]*2;
    for (int i = 1; i <= n; i++) {
        lnt x;	scanf("%lld", &x);
        for (int j = MAX_N; j >= 0; j--)	if (pow[j]&x) {
            if (base[j])	x ^= base[j];
            else {base[j] = x;	break;}
        }
    }
    lnt ans = 0;
    for (int i = MAX_N; i >= 0; i--)	if ((ans^pow[i]) > ans)	ans ^= base[i];
    printf("%lld", ans);
    return 0;
}

Lucas

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#define MAX_P 100000
using namespace std;
typedef long long lnt;
lnt f[MAX_P+5] = {1};
void init(lnt p) {for (int i = 1; i <= MAX_P; i++)    f[i] = f[i-1]*i%p;}
lnt FLT(lnt x, lnt p) {
    lnt ret = 1;	x %= p;
    for (int k = p-2; k; k >>= 1)	ret = k%2 ? ret*x%p : ret, x = x*x%p;
    return ret;
}
lnt lucas(lnt n, lnt m, lnt p) {return m ? (n%p >= m%p ? f[n%p]*FLT(f[m%p]*f[n%p-m%p], p)*lucas(n/p, m/p, p)%p : 0) : 1;}
int main() {
    int T;	scanf("%d", &T);
    while (T--) {
        lnt n, m, p;	scanf("%lld%lld%lld", &n, &m, &p);
        init(p), printf("%lld\n", lucas(n+m, min(n, m), p)%p);
    }
    return 0;
}

Matrix Fast Power

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100
#define MOD 1000000007
using namespace std;
int n;
struct Matrix {
    long long ele[MAX_N][MAX_N];
    inline Matrix operator * (const Matrix &x) const {
        Matrix ret;
        memset(ret.ele, 0, sizeof(ret.ele));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    ret.ele[i][j] = (ret.ele[i][j]+ele[i][k]*x.ele[k][j])%MOD;
        return ret;
    }
};
Matrix Power(Matrix a, long long k) {
    if (k == 1)    return a;
    Matrix ret = Power(a, k/2);
    if (k%2)    return a*ret*ret;
    return ret*ret;
}
int main() {
    long long k;
    Matrix a;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a.ele[i][j];
    a = Power(a, k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << a.ele[i][j] << " ";
        cout << endl;
    }
    return 0;
}

Prime Sieve

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
#include <bits/stdc++.h>
#define MAX_N 10000000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;    bool NotPri[MAX_N+5];
int pri[MAX_N+5], mu[MAX_N+5], phi[MAX_N+5], cnt;
void init() {
    NotPri[1] = true, mu[1] = phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1, phi[i] = i-1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > n) break;	NotPri[i*pri[j]] = true;
            if (i%pri[j]) phi[i*pri[j]] = phi[i]*phi[pri[j]], mu[i*pri[j]] = -mu[i];
            else {phi[i*pri[j]] = phi[i]*pri[j], mu[i*pri[j]] = 0; break;}
        }
    }
}
int main() {
    read(n), read(m), init();
    for (int x; m; m--)
        read(x), puts(NotPri[x] ? "No" : "Yes");
    return 0;
}
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
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n;
double s, t;
double a[14];
double calc(double x) {
    double tot = 0, tmp = 1;
    for (int i = 0; i <= n; i++) {
        tot += tmp*a[i];
        tmp *= x;
    }
    return tot;
}
void f(double l, double r) {
    if (abs(r-l) <= 0.000001) {
        printf("%.5f", l);
        return;
    }
    double ml = (2*l+r)/3, mr = (l+2*r)/3;
    if (calc(ml) > calc(mr)) {
        f(l, mr);
    } else {
        f(ml, r);
    }
}
int main() {
    cin >> n >> s >> t;
    for (int i = n; i >= 0; i--) {
        cin >> a[i];
    }
    f(s, t);
    return 0;
}

Fast Fourier Transformation

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
#include <bits/stdc++.h>
#define MAX_N 1000000
using namespace std;
typedef double dnt;
const dnt Pi = acos(-1);
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct Complex {dnt r, i;} a[(MAX_N<<2)+5], b[(MAX_N<<2)+5], c[(MAX_N<<2)+5];
Complex operator + (Complex x, Complex y) {return (Complex){x.r+y.r, x.i+y.i};}
Complex operator - (Complex x, Complex y) {return (Complex){x.r-y.r, x.i-y.i};}
Complex operator * (Complex x, Complex y) {return (Complex){x.r*y.r-x.i*y.i, x.r*y.i+x.i*y.r};}
void Rader(Complex *s, int l) {
    for (int i = 1, j = l/2, k; i < l-1; i++) {
        if (i < j) swap(s[i], s[j]);	k = l/2;
        while (j >= k) j -= k, k >>= 1;	j += k;
    }
}
void FFT(Complex *s, int l, int f) {
    Rader(s, l);	Complex wn, w;
    for (int i = 2; i <= l; i <<= 1) {
        wn = (Complex){cos(2*Pi/i), f*sin(2*Pi/i)};
        for (int j = 0; j < l; j += i) {
            w = (Complex){1, 0};
            for (int k = j; k < j+i/2; k++, w = w*wn) {
                Complex x = s[k], y = w*s[k+i/2];
                s[k] = x+y, s[k+i/2] = x-y;
            }
        }
    }
    if (f == -1) for (int i = 0; i <= l; i++) s[i].r /= l;
}
int main() {
    int n, m;	read(n), read(m);
    for (int i = 0, x; i <= n; i++) read(x), a[i].r = x;
    for (int i = 0, x; i <= m; i++) read(x), b[i].r = x;
    int l;	for (l = 1; l <= n+m; l <<= 1) ;	FFT(a, l, 1), FFT(b, l, 1);
    for (int i = 0; i <= l; i++) c[i] = a[i]*b[i];	FFT(c, l, -1);
    for (int i = 0; i <= n+m; i++) printf("%d ", (int)(c[i].r+0.5));
    return 0;
}

Data Structure

Heap

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
#include <iostream>
using namespace std;
int n, heap[1000000+5], size = 0;
void insert(int x) {
    size++;
    heap[size] = x;
    int current = size;
    int father = current/2;
    while (father > 0 && heap[father] > heap[current]) {
        swap(heap[father], heap[current]);
        current = father;
        father = current/2;
    }
}
void pop() {
    heap[1] = heap[size];
    size--;
    int current = 1;
    int child = current*2;
    if (child < size && heap[child] > heap[child+1])    child++;
    while (child <= size && heap[current] > heap[child]) {
        swap(heap[current], heap[child]);
        current = child;
        child = 2*current;
        if (child < size && heap[child] > heap[child+1])    child++;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int f;
        cin >> f;
        if (f == 1) {
            int x;
            cin >> x;
            insert(x);
        } else if (f == 2) {
            cout << heap[1] << endl;
        } else {
            pop();
        }
    }
    return 0;
}

Mergeable Heap

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
#include <iostream>
#include <cstdio>
#define MAX_N 100000
using namespace std;
struct node {int val, dis, ls, rs;} heap[MAX_N+5];
int n, m, fa[MAX_N+5];
int getf(int x) {return fa[x] == x ? fa[x] : getf(fa[x]);}
int merge(int a, int b) {
    if (!a || !b)	return a^b;
    if (heap[a].val > heap[b].val || (heap[a].val == heap[b].val && a > b))	swap(a, b);
    heap[a].rs = merge(heap[a].rs, b), fa[heap[a].rs] = a;
    if (heap[heap[a].rs].dis > heap[heap[a].ls].dis)	swap(heap[a].ls, heap[a].rs);
    heap[a].dis = heap[a].rs == 0 ? 0 : heap[heap[a].rs].dis+1;	return a;
}
int pop(int a) {
    int l = heap[a].ls, r = heap[a].rs;
    heap[a].ls = heap[a].rs = heap[a].val = 0, fa[l] = l, fa[r] = r;
    return merge(l, r);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	scanf("%d", &heap[i].val), fa[i] = i;
    while (m--) {
        int opt;	scanf("%d", &opt);
        if (opt == 1) {
            int x, y;	scanf("%d%d", &x, &y), x = getf(x), y = getf(y);
            if (heap[x].val && heap[y].val && x != y)	merge(x, y);
        }
        if (opt == 2) {
            int x;	scanf("%d", &x), x = getf(x);
            if (!heap[x].val)	printf("-1\n");
            else	printf("%d\n", heap[x].val), pop(x);
        }
    }
    return 0;
}

Binary Indexed Tree

Version 1

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 500000
using namespace std;
int n, m;
int tree[MAX_N+5];
int lowbit(int x) {
    return x&(-x);
}
void modify(int pos, int x) {
    while (pos <= n) {
        tree[pos] += x;
        pos += lowbit(pos);
    }
}
long long query(int t) {
    long long tot = 0;
    while (t > 0) {
        tot += tree[t];
        t -= lowbit(t);
    }
    return tot;
}
int main() {
    memset(tree, 0, sizeof(tree));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        modify(i, tmp);
    }
    for (int i = 0; i < m; i++) {
        int f, a, b;
        cin >> f >> a >> b;
        if (f == 1) {
            modify(a, b);
        } else {
            cout << query(b)-query(a-1) << endl;
        }
    }
    return 0;
}

Version 2

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 500000
using namespace std;
int n, m;
int tree[MAX_N+5];
int lowbit(int x) {
    return x&(-x);
}
void modify(int pos, int x) {
    while (pos <= n) {
        tree[pos] += x;
        pos += lowbit(pos);
    }
}
long long query(int pos) {
    long long tot = 0;
    while (pos > 0) {
        tot += tree[pos];
        pos -= lowbit(pos);
    }
    return tot;
}
int main() {
    memset(tree, 0, sizeof(tree));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        modify(i, x);
        modify(i+1, -x);
    }
    for (int i = 0; i < m; i++) {
        int f;
        cin >> f;
        if (f == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            modify(l, x);
            modify(r+1, -x);
        } else {
            int x;
            cin >> x;
            cout << query(x) << endl;
        }
    }
    return 0;
}

Segment Tree

Version 1

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100000
using namespace std;
int n, k;
long long tree[MAX_N*4+50], tag[MAX_N*4+50];
void updata(int v) {
    tree[v] = tree[v*2]+tree[v*2+1];
}
void downtag(int v, int s, int t) {
    tag[v*2] += tag[v];
    tag[v*2+1] += tag[v];
    int m = (s+t)/2;
    tree[v*2] += tag[v]*(m-s+1);
    tree[v*2+1] += tag[v]*(t-m);
    tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        tree[v] += x*(t-s+1);
        tag[v] += x;
        return;
    }
    int m = (s+t)/2;
    downtag(v, s, t);
    if (l <= m) {
        modify(v*2, s, m, l, r, x);
    }
    if (r >= m+1) {
        modify(v*2+1, m+1, t, l, r, x);
    }
    updata(v);
}
void build(int v, int s, int t) {
    if (s == t) {
        cin >> tree[v];
        return;
    }
    int m = (s+t)/2;
    build(v*2, s, m);
    build(v*2+1, m+1, t);
    updata(v);
}
long long query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) {
        return tree[v];
    }
    int m = (s+t)/2;
    downtag(v, s, t);
    long long ret = 0;
    if (l <= m) {
        ret += query(v*2, s, m, l, r);
    }
    if (r >= m+1) {
        ret += query(v*2+1, m+1, t, l, r);
    }
    updata(v);
    return ret;
}
int main() {
    cin >> n >> k;
    build(1, 1, n);
    for (int i = 0; i < k; i++) {
        int f, l, r, x;
        cin >> f;
        if (f == 1) {
            cin >> l >> r >> x;
            modify(1, 1, n, l, r, x);
        } else {
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << endl;
        }
    }
    return 0;
}

Version 2

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 100000
#define ll long long
using namespace std;
int n, m;
ll p;
ll tree[MAX_N*4+5], mul[MAX_N*4+5], add[MAX_N*4+5];
void updata(int v) {
    tree[v] = (tree[v*2]+tree[v*2+1])%p;
}
void downtag(int v, int s, int t, int mid) {
    if (mul[v] == 1 && add[v] == 0)	return;
    mul[v*2] = mul[v*2]*mul[v]%p;
    add[v*2] = (add[v*2]*mul[v]%p+add[v])%p;
    tree[v*2] = (tree[v*2]*mul[v]%p+add[v]*(ll)(mid-s+1)%p)%p;
    mul[v*2+1] = mul[v*2+1]*mul[v]%p;
    add[v*2+1] = (add[v*2+1]*mul[v]%p+add[v])%p;
    tree[v*2+1] = (tree[v*2+1]*mul[v]%p+add[v]*(ll)(t-mid)%p)%p;
    mul[v] = 1;
    add[v] = 0;
    return;
}
void create(int v, int s, int t) {
    mul[v] = 1;
    add[v] = 0;
    if (s == t) {
        cin >> tree[v];
        tree[v] %= p;
        return;
    }
    int mid = (s+t)/2;
    create(v*2, s, mid);
    create(v*2+1, mid+1, t);
    updata(v);
}
void modify1(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        add[v] = (add[v]+(ll)x)%p;
        tree[v] = (tree[v]+(ll)x*(ll)(t-s+1)%p)%p;
        return;
    }
    int mid = (s+t)/2;
    downtag(v, s, t, mid);
    if (l <= mid) {
        modify1(v*2, s, mid, l, r, x);
    }
    if (r >= mid+1) {
        modify1(v*2+1, mid+1, t, l, r, x);
    }
    updata(v);
}
void modify2(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        mul[v] = mul[v]*(ll)x%p;
        add[v] = add[v]*(ll)x%p;
        tree[v] = tree[v]*(ll)x%p;
        return; 
    }
    int mid = (s+t)/2;
    downtag(v, s, t, mid);
    if (l <= mid) {
        modify2(v*2, s, mid, l, r, x);
    }
    if (r >= mid+1) {
        modify2(v*2+1, mid+1, t, l, r, x);
    }
    updata(v);
}
ll query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) {
        return tree[v];
    }
    int mid = (s+t)/2;
    ll ret = 0;
    downtag(v, s, t, mid);
    if (l <= mid) {
        ret = (ret+query(v*2, s, mid, l, r))%p;
    }
    if (r >= mid+1) {
        ret = (ret+query(v*2+1, mid+1, t, l, r))%p;
    }
    updata(v);
    return ret;
}
int main() {
    cin >> n >> m >> p;
    create(1, 1, n);
    for (int i = 0; i < m; i++) {
        int f;
        cin >> f;
        if (f == 1) {
            int l, r, x;
            cin >> l >> r >> x;
            modify2(1, 1, n, l, r, x%p);
        } else if (f == 2) {
            int l, r, x;
            cin >> l >> r >> x;
            modify1(1, 1, n, l, r, x%p);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << endl;
        }
    }
    return 0;
}

Sparse 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
#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX_N 100000
using namespace std;
int n, m, num[MAX_N+5], mx[MAX_N+5][20];
void setTable() {
    for (int i = 1; i <= n; i++)	mx[i][0] = num[i];
    for (int j = 1; (1<<j) <= n; j++)
        for (int i = 1; i+(1<<j)-1 <= n; i++)
            mx[i][j] = max(mx[i][j-1], mx[i+(1<<j-1)][j-1]);
}
int query(int l, int r) {
    int range = (int)(log(r-l+1)/log(2));
    return max(mx[l][range], mx[r-(1<<range)+1][range]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	scanf("%d", &num[i]);
    setTable();
    while (m--) {
        int l, r;	scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }
    return 0;
}

Sustainable Segment 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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 200000
using namespace std;
int n, m, num[MAX_N+5], hash[MAX_N+5], tot, root[MAX_N+5], cnt;
struct pre {int id, val;} p[MAX_N+5];
bool cmp (const pre &a, const pre &b) {return a.val < b.val;}
struct node {int ls, rs, val;} tr[MAX_N*50];
void updata(int v) {tr[v].val = tr[tr[v].ls].val+tr[tr[v].rs].val;}
void build(int v, int s, int t) {
    if (s == t)	return;	int mid = s+t>>1;
    tr[v].ls = ++cnt, tr[v].rs = ++cnt;
    build(tr[v].ls, s, mid), build(tr[v].rs, mid+1, t);
}
void modify(int v, int o, int s, int t, int x) {
    tr[v] = tr[o];	if (s == t) {tr[v].val++;	return;}
    int mid = s+t>>1;
    if (x <= mid)	modify(tr[v].ls = ++cnt, tr[o].ls, s, mid, x);
    else	modify(tr[v].rs = ++cnt, tr[o].rs, mid+1, t, x);
    updata(v);
}
int query(int v1, int v2, int s, int t, int k) {
    if (s == t)	return s;
    int mid = s+t>>1, tmp = tr[tr[v2].ls].val-tr[tr[v1].ls].val;
    if (k <= tmp)	return query(tr[v1].ls, tr[v2].ls, s, mid, k);
    else	return query(tr[v1].rs, tr[v2].rs, mid+1, t, k-tmp);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)	p[i].id = i, scanf("%d", &p[i].val);
    sort(p+1, p+n+1, cmp);
    for (int i = 1; i <= n; i++) {if (p[i].val != p[i-1].val || i == 1)	hash[++tot] = p[i].val;	num[p[i].id] = tot;}
    root[0] = ++cnt, build(root[0], 1, tot);
    for (int i = 1; i <= n; i++)	root[i] = ++cnt, modify(root[i], root[i-1], 1, tot, num[i]);
    while (m--) {
        int l, r, k;	scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", hash[query(root[l-1], root[r], 1, tot, k)]);
    }
    return 0;
}

Treap

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MAX_N 100000
using namespace std;
struct TNode {
    TNode* s[2];
    int val, k, size;
    TNode() {}
    TNode(int _val, TNode* _s) {val = _val, s[0] = s[1] = _s, k = rand(), size = 1;}
    void updata() {size = s[0]->size+s[1]->size+1;}
} nil, tr[MAX_N+5], *null, *root, *cnt;
typedef TNode* P_TNode;
void init() {
    srand(19260817);
    nil = TNode(0, NULL), null = &nil;
    null->s[0] = null->s[1] = null, null->size = 0;
    cnt = tr, root = null;
}
P_TNode newnode(int val) {
    *cnt = TNode(val, null);
    return cnt++;
}
P_TNode merge(P_TNode a, P_TNode b) {
    if (a == null)    return b;
    if (b == null)    return a;
    if (a->k > b->k) {a->s[1] = merge(a->s[1], b), a->updata(); return a;}
    if (a->k <= b->k) {b->s[0] = merge(a, b->s[0]), b->updata(); return b;}
}
void split(P_TNode v, int val, P_TNode &ls, P_TNode &rs) {
    if (v == null) {ls = rs = null; return;}
    if (val < v->val) {rs = v; split(rs->s[0], val, ls, rs->s[0]);}
    if (val >= v->val) {ls = v;    split(ls->s[1], val, ls->s[1], rs);}
    v->updata();
}
void insert(int val) {
    P_TNode ls, rs;
    split(root, val, ls, rs);
    root = merge(merge(ls, newnode(val)), rs);
}
void remove(int val) {
    P_TNode ls, mids, rs;
    split(root, val-1, ls, rs);
    split(rs, val, mids, rs);
    root = merge(ls, merge(merge(mids->s[0], mids->s[1]), rs));
}
int get_rank(int val) {
    P_TNode ls, rs;
    split(root, val-1, ls, rs);
    int ret = ls->size+1;
    root = merge(ls, rs);
    return ret;
}
int get_kth(P_TNode v, int k) {
    if (k <= v->s[0]->size)    return get_kth(v->s[0], k);
    if (k > v->s[0]->size+1)    return get_kth(v->s[1], k-v->s[0]->size-1);
    return v->val;
}
int get_nearest(P_TNode v, int sn) {
    while (v->s[sn] != null)    v = v->s[sn];
    return v->val;
}
int predecessor(int val) {
    P_TNode ls, rs;
    split(root, val-1, ls, rs);
    int ret = get_nearest(ls, 1);
    root = merge(ls, rs);
    return ret;
}
int successor(int val) {
    P_TNode ls, rs;
    split(root, val, ls, rs);
    int ret = get_nearest(rs, 0);
    root = merge(ls, rs);
    return ret;
}
int main() {
    init();
    int n, opt, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &opt, &x);
        if (opt == 1)    insert(x);
        if (opt == 2)    remove(x);
        if (opt == 3)    printf("%d\n", get_rank(x));
        if (opt == 4)    printf("%d\n", get_kth(root, x));
        if (opt == 5)    printf("%d\n", predecessor(x));
        if (opt == 6)    printf("%d\n", successor(x));
    }
    return 0;
}

Splay

Normal

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
#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define flag (cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;	int val, w, sz;
    void updata() {sz = w+(s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0);}
};
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = _val, v->w = v->sz = 1;
        return v;
    }
    SplayTree() {
        rt = newnode(-INF), rt->s[1] = newnode(INF);
        rt->s[1]->fa = rt, rt->updata();
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* predecessor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val > cur->val])
            if (cur->val < _val) cpy = cur;
        return cpy;
    }
    SplayNode* successor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val >= cur->val])
            if (cur->val > _val) cpy = cur;
        return cpy;
    }
    void insert(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) suc->s[0]->w++, suc->s[0]->sz++;
        else suc->s[0] = newnode(_val), suc->s[0]->fa = suc;
        suc->updata(), rt->updata();
    }
    void remove(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        suc->s[0]->w--, suc->s[0]->sz--;
        if (!suc->s[0]->w) suc->s[0] = NULL;
        suc->updata(), rt->updata();
    }
    int get_rank(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc == NULL) return rt->sz;
        return rt->sz-suc->sz;
    }
    SplayNode* get_kth(SplayNode* v, int k) {
        int lsz = v->s[0] ? v->s[0]->sz : 0;
        if (k <= lsz) return get_kth(v->s[0], k);
        if (k > lsz+v->w) return get_kth(v->s[1], k-lsz-v->w);
        return v;
    }
} BBST;
int main() {
    int n, opt, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &opt, &x);
        if (opt == 1)	BBST.insert(x);
        if (opt == 2)	BBST.remove(x);
        if (opt == 3)	printf("%d\n", BBST.get_rank(x));
        if (opt == 4)	printf("%d\n", BBST.get_kth(BBST.rt, x+1)->val);
        if (opt == 5)	printf("%d\n", BBST.predecessor(x)->val);
        if (opt == 6)	printf("%d\n", BBST.successor(x)->val);
    }
    return 0;
}

Reverse

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
#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
#define flag (cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;
    int val, w, sz;	bool rev;
    void updata() {sz = w+(s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0);}
    void downtag() {
        if (!rev) return;	rev = false, swap(s[0], s[1]);
        if (s[0]) s[0]->rev ^= 1;	if (s[1]) s[1]->rev ^= 1;
    }
};
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = _val, v->sz = v->w = 1;
        v->rev = false;	return v;
    }
    SplayTree(int n) {
        rt = newnode(-INF), rt->s[1] = newnode(INF);
        rt->s[1]->fa = rt, rt->updata();
        for (int i = 1; i <= n; i++) insert(i);
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* predecessor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val > cur->val])
            if (cur->val < _val) cpy = cur;
        return cpy;
    }
    SplayNode* successor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val >= cur->val])
            if (cur->val > _val) cpy = cur;
        return cpy;
    }
    void insert(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) suc->s[0]->w++, suc->s[0]->sz++;
        else suc->s[0] = newnode(_val), suc->s[0]->fa = suc;
        suc->updata(), rt->updata();
    }
    void reverse(int l, int r) {
        SplayNode *nl = get_kth(rt, l), *nr = get_kth(rt, r+2);
        splay(nl, rt), splay(nr, rt->s[1]), nr->s[0]->rev ^= 1;
    }
    SplayNode* get_kth(SplayNode* v, int k) {
        v->downtag();
        int lsz = v->s[0] == NULL ? 0 : v->s[0]->sz;
        if (k <= lsz) return get_kth(v->s[0], k);
        if (k > lsz+v->w) return get_kth(v->s[1], k-lsz-v->w);
        return v;
    }
    void output(SplayNode* v) {
        if (v == NULL) return;	v->downtag(), output(v->s[0]);
        if (v->val != -INF && v->val != INF) printf("%d ", v->val);
        output(v->s[1]);
    }
};
int main() {
    int n, m;	scanf("%d%d", &n, &m);	SplayTree BBST(n);
    for (int i = 1, l, r; i <= m; i++)	scanf("%d%d", &l, &r), BBST.reverse(l, r);
    return BBST.output(BBST.rt), 0;
}

Range 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
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
#include <bits/stdc++.h>
#define MAX_N 200000
#define INF 2147483647
#define mid ((s+t)>>1)
#define flag (cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
int n, m, c[MAX_N+5];
struct SplayNode {
    SplayNode *s[2], *fa;	int val, w, sz;
    void updata() {sz = w+(s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0);}
};
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = _val, v->w = v->sz = 1;
        return v;
    }
    SplayTree() {
        rt = newnode(-INF), rt->s[1] = newnode(INF);
        rt->s[1]->fa = rt, rt->updata();
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* predecessor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val > cur->val])
            if (cur->val < _val) cpy = cur;
        return cpy;
    }
    SplayNode* successor(int _val) {
        SplayNode *cur = rt, *cpy = rt;
        for (; cur; cur = cur->s[_val >= cur->val])
            if (cur->val > _val) cpy = cur;
        return cpy;
    }
    void insert(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc->s[0]) suc->s[0]->w++, suc->s[0]->sz++;
        else suc->s[0] = newnode(_val), suc->s[0]->fa = suc;
        suc->updata(), rt->updata();
    }
    void remove(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        suc->s[0]->w--, suc->s[0]->sz--;
        if (!suc->s[0]->w) suc->s[0] = NULL;
        suc->updata(), rt->updata();
    }
    int get_rank(int _val) {
        SplayNode* pre = predecessor(_val);
        SplayNode* suc = successor(_val);
        splay(pre, rt), splay(suc, rt->s[1]);
        if (suc == NULL) return rt->sz-1;
        return rt->sz-suc->sz-1;
    }
} tr[(MAX_N<<2)+5];
void ins(int v, int s, int t, int p, int x) {
    tr[v].insert(x);	if (s == t) return;
    if (p <= mid) ins(v<<1, s, mid, p, x);
    else ins(v<<1|1, mid+1, t, p, x);
}
void modify(int v, int s, int t, int p, int x, int o) {
    tr[v].remove(o), tr[v].insert(x);	if (s == t) return;
    if (p <= mid) modify(v<<1, s, mid, p, x, o);
    else modify(v<<1|1, mid+1, t, p, x, o);
}
int query(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) return tr[v].get_rank(x);	int ret = 0;
    if (l <= mid) ret += query(v<<1, s, mid, l, r, x);
    if (r >= mid+1) ret += query(v<<1|1, mid+1, t, l, r, x);
    return ret;
}
int get_ind(int l, int r, int k) {
    int s = 0, t = INF, ret = -1;
    while (s <= t)
        if (query(1, 1, n, l, r, mid) >= k) t = mid-1;
        else ret = mid, s = mid+1;
    return ret;
}
int get_pre(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) return tr[v].predecessor(x)->val;	int ret = -INF;
    if (l <= mid) ret = max(ret, get_pre(v<<1, s, mid, l, r, x));
    if (r >= mid+1) ret = max(ret, get_pre(v<<1|1, mid+1, t, l, r, x));
    return ret;
}
int get_suc(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) return tr[v].successor(x)->val;	int ret = INF;
    if (l <= mid) ret = min(ret, get_suc(v<<1, s, mid, l, r, x));
    if (r >= mid+1) ret = min(ret, get_suc(v<<1|1, mid+1, t, l, r, x));
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", c+i), ins(1, 1, n, i, c[i]);
    while (m--) {
        int opt, l, r, p, k, x;	scanf("%d", &opt);
        if (opt == 1) scanf("%d%d%d", &l, &r, &x), printf("%d\n", query(1, 1, n, l, r, x)+1);
        if (opt == 2) scanf("%d%d%d", &l, &r, &k), printf("%d\n", get_ind(l, r, k));
        if (opt == 3) scanf("%d%d", &p, &x), modify(1, 1, n, p, x, c[p]), c[p] = x;
        if (opt == 4) scanf("%d%d%d", &l, &r, &x), printf("%d\n", get_pre(1, 1, n, l, r, x));
        if (opt == 5) scanf("%d%d%d", &l, &r, &x), printf("%d\n", get_suc(1, 1, n, l, r, x));
    }
}

Heavy Path Decomposition

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
#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 100000
using namespace std;
int n, m, r, p, ind;
vector <int> G[MAX_N+5];
int c[MAX_N+5];
int dep[MAX_N+5], fa[MAX_N+5], size[MAX_N+5], son[MAX_N+5];
int top[MAX_N+5], dfn[MAX_N+5], last[MAX_N+5];
int seg[(MAX_N<<2)+5], tag[(MAX_N<<2)+5];
void DFS1(int u) {
    size[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa[u])	continue;
        dep[v] = dep[u]+1;
        fa[v] = u;
        DFS1(v);
        size[u] += size[v];
        if (!son[u] || size[son[u]] < size[v])	son[u] = v;
    }
}
void DFS2(int u, int tp) {
    top[u] = tp, dfn[u] = ++ind;
    if (son[u])	DFS2(son[u], tp);
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa[u] || v == son[u])	continue;
        DFS2(v, v);
    }
    last[u] = ind;
}
void updata(int v) {seg[v] = (seg[v<<1]+seg[v<<1|1])%p;}
void downtag(int v, int s, int t) {
    if (!tag[v])	return;
    int mid = s+t>>1;
    seg[v<<1] = (seg[v<<1]+tag[v]*(mid-s+1))%p;
    seg[v<<1|1] = (seg[v<<1|1]+tag[v]*(t-mid))%p;
    tag[v<<1] = (tag[v<<1]+tag[v])%p;
    tag[v<<1|1] = (tag[v<<1|1]+tag[v])%p;
    tag[v] = 0;
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {seg[v] = (seg[v]+x*(t-s+1))%p, tag[v] = (tag[v]+x)%p;	return;}
    downtag(v, s, t);
    int mid = s+t>>1;
    if (l <= mid)	modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1)	modify(v<<1|1, mid+1, t, l, r, x);
    updata(v);
}
int query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r)	return seg[v];
    downtag(v, s, t);
    int mid = s+t>>1, ret = 0;
    if (l <= mid)	ret = (ret+query(v<<1, s, mid, l, r))%p;
    if (r >= mid+1)	ret = (ret+query(v<<1|1, mid+1, t, l, r))%p;
    updata(v);
    return ret;
}
void solve1(int x, int y, int z) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])	swap(x, y);
        modify(1, 1, n, dfn[top[x]], dfn[x], z);
        x = fa[top[x]];
    }
    modify(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y]), z);
}
int solve2(int x, int y) {
    int ret = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]])	swap(x, y);
        ret = (ret+query(1, 1, n, dfn[top[x]], dfn[x]))%p;
        x = fa[top[x]];
    }
    ret = (ret+query(1, 1, n, min(dfn[x], dfn[y]), max(dfn[x], dfn[y])))%p;
    return ret;
}
void solve3(int x, int z) {modify(1, 1, n, dfn[x], last[x], z);}
int solve4(int x) {return query(1, 1, n, dfn[x], last[x]);}
int main() {
    scanf("%d%d%d%d", &n, &m, &r, &p);
    for (int i = 1; i <= n; i++)	scanf("%d", &c[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    DFS1(r);
    DFS2(r, r);
    for (int i = 1; i <= n; i++)	modify(1, 1, n, dfn[i], dfn[i], c[i]);
    while (m--) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            solve1(x, y, z);
        }
        if (opt == 2) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", solve2(x, y));
        }
        if (opt == 3) {
            int x, z;
            scanf("%d%d", &x, &z);
            solve3(x, z);
        }
        if (opt == 4) {
            int x;
            scanf("%d", &x);
            printf("%d\n", solve4(x));
        }
    }
    return 0;
}
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
#include <bits/stdc++.h>
#define MAX_N 300000
#define INF 0x7f7f7f7f
#define flag (!tar(cur->fa->fa)&&cur->fa->fa->s[sn]==cur->fa)
using namespace std;
struct SplayNode {
    SplayNode *s[2], *fa;	int val, sum;	bool rev;
    void updata() {sum = val^(s[0]?s[0]->sum:0)^(s[1]?s[1]->sum:0);}
    void downtag() {
        if (fa && (fa->s[0] == this || fa->s[1] == this)) fa->downtag();
        if (rev && s[0]) swap(s[0]->s[0], s[0]->s[1]), s[0]->rev ^= 1;
        if (rev && s[1]) swap(s[1]->s[0], s[1]->s[1]), s[1]->rev ^= 1;
        rev = false;
    }
} *tr[MAX_N+5];
struct LinkCutTree {
    SplayNode* newnode(int _val) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->val = v->sum = _val, v->rev = 0;
        return v;
    }
    SplayNode* get_rt(SplayNode* v) {for (; v->fa; v = v->fa) ;	return v;}
    bool tar(SplayNode* v) {return (v&&v->fa==NULL)||(v&&v->fa->s[0]!=v&&v->fa->s[1]!=v);}
    LinkCutTree(int n) {for (int i=1,_val;i<=n;i++) scanf("%d", &_val), tr[i]=newnode(_val);}
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa && !tar(f)) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->updata(), v->updata();
    }
    void splay(SplayNode* cur) {
        cur->downtag();
        while (!tar(cur) && !tar(cur->fa)) {
            bool sn = cur->fa->s[1] == cur;
            if flag rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (!tar(cur) && tar(cur->fa))
            rotate(cur, cur->fa->s[0] == cur);
        cur->updata();
    }
    void access(SplayNode* cur) {
        for (SplayNode* cpy = NULL; cur; cpy = cur, cur = cur->fa)
            splay(cur), cur->s[1] = cpy, cur->updata();
    }
    void mroot(SplayNode* v) {
        access(v), splay(v);
        swap(v->s[0], v->s[1]), v->rev ^= 1;
    }
    void link(SplayNode* u, SplayNode* v) {
        if (get_rt(u) == get_rt(v)) return;
        mroot(u), u->fa = v;
    }
    void cut(SplayNode* u, SplayNode* v) {
        if (u == v || get_rt(u) != get_rt(v)) return;
        mroot(u), access(v), splay(v);
        if (v->s[0] == u) u->fa = v->s[0] = NULL, v->updata();
    }
    void modify(SplayNode* v, int _val) {
        splay(v), v->val = _val, v->updata();
    }
    int query(SplayNode* u, SplayNode* v) {
        mroot(u), access(v), splay(v);
        return v->sum;
    }
};
int main() {
    int n, m;	scanf("%d%d", &n, &m);
    LinkCutTree LCT(n);
    while (m--) {
        int opt, x, y;	scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0) printf("%d\n", LCT.query(tr[x], tr[y]));
        if (opt == 1) LCT.link(tr[x], tr[y]);
        if (opt == 2) LCT.cut(tr[x], tr[y]);
        if (opt == 3) LCT.modify(tr[x], y);
    }
    return 0;
}

String

Knuth-Morris-Pratt

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
#include <iostream>
#include <cstdio>
#include <string>
#define MAX_M 1000
using namespace std;
int next[MAX_M];
void CalcNext(string& s) {
    int m = s.length();
    int begin = 1, matched = 0;
    while (begin+matched < m) {
        if (s[begin+matched] == s[matched]) {
            matched++;
            next[begin+matched-1] = matched;
        } else {
            if (matched == 0) {
                begin++;
            } else {
                begin += matched-next[matched-1];
                matched = next[matched-1];
            }
        }
    }
}
void KMP(string& T, string& P) {
    int n = T.length(), m = P.length();
    int begin = 0, matched = 0;
    while (begin <= n-m) {
        if (matched < m && T[begin+matched] == P[matched]) {
            matched++;
            if (matched == m) {
                cout << begin+1 << endl;
            }
        } else {
            if (matched == 0) {
                begin++;
            } else {
                begin += matched-next[matched-1];
                matched = next[matched-1];
            }
        }
    }
}
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    CalcNext(s2);
    KMP(s1, s2);
    for (int i = 0; i < s2.length(); i++) {
        cout << next[i] << " ";
    }
    return 0;
}

Manacher

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_L 11000000
using namespace std;
char s[MAX_L*2+5];
int f[MAX_L*2+5];
int manacher (char* s0) {
    int len = strlen(s0);
    for (int i = 0; i < len; i++)	s[i*2+1] = '#', s[i*2+2] = s0[i];
    s[len = len*2+1] = '#';
    int pos = 0, r = 0, ret = 0;
    for (int i = 1; i <= len; i++) {
        f[i] = (i < r) ? min(f[2*pos-i], r-i) : 1;
        while (i-f[i] >= 1 && i+f[i] <= len && s[i-f[i]] == s[i+f[i]])	f[i]++;
        if (i+f[i] > r)	pos = i, r = i+f[i];
        ret = max(ret, f[i]-1);
    }
    return ret;
}
int main() {
    char s0[MAX_L+5];	scanf("%s", s0);
    printf("%d\n", manacher(s0));
    return 0;
}

Aho-Corasick Automaton

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define DICNUM 26
#define MAX_LETTER 10500
#define MAX_LENGTH 1000000
using namespace std;
char P[155][75], T[MAX_LENGTH+5];
int root = 1, cnt, trie[MAX_LETTER+5][DICNUM], fail[MAX_LETTER+5], end[MAX_LETTER+5], tot[155];
void init() {
    memset(P, 0, sizeof(P)), memset(T, 0, sizeof(T)), memset(tot, 0, sizeof(tot));
    for (int i = 1; i <= cnt; i++)	memset(trie[i], 0, sizeof(trie[i])), fail[i] = end[i] = 0;	cnt = 1;
}
void insert(int id, char s[]) {
    int cur = 1, len = strlen(s);
    for (int i = 0; i < len; cur = trie[cur][s[i++]-'a'])
        if (!trie[cur][s[i]-'a'])	trie[cur][s[i]-'a'] = ++cnt;
    end[cur] = id;
}
void SetFail() {
    queue <int> que;	que.push(root);
    while (!que.empty()) {
        int u = que.front();	que.pop();
        for (int i = 0; i < DICNUM; i++)
            if (trie[u][i])	fail[trie[u][i]] = trie[fail[u]][i], que.push(trie[u][i]);
            else trie[u][i] = trie[fail[u]][i];
    }
}
void query() {
    int cur = root, index, len = strlen(T);
    for (int i = 0; i < len; i++) {
        index = T[i]-'a';
        while (!trie[cur][index])	cur = fail[cur];
        cur = trie[cur][index];
        for (int j = cur; j; j = fail[j])	tot[end[j]]++;
    }
}
int main() {
    int n;
    for (int i = 0; i < DICNUM; i++)	trie[0][i] = root;
    while (scanf("%d", &n) && n) {
        init();
        for (int i = 1; i <= n; i++)	scanf("%s", P[i]), insert(i, P[i]);
        SetFail(), scanf("%s", T), query();
        int ans = 0;
        for (int i = 1; i <= n; i++)	ans = max(ans, tot[i]);
        printf("%d\n", ans);
        for (int i = 1; i <= n; i++)	if (tot[i] == ans)	printf("%s\n", P[i]);
    }
    return 0;
}

Hash 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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <string>
#define size 15000
using namespace std;
int n, cnt = 0;
string tmp;
string hash[size];
int calc(string& index) {
    int ret = 0;
    for (int i = 0; i < index.length(); i++) {
        ret = (ret*256+index[i]+128)%size;
    }
    return ret;
}
bool search(string& index, int& pos) {
    pos = calc(index);
    while (hash[pos] != "" && hash[pos] != index) {
        pos = (pos+1)%size;
    }
    if (hash[pos] == index) {
        return true;
    } else {
        return false;
    }
}
int insert(string& index) {
    int pos;
    if (search(index, pos)) {
        return 0;
    } else {
        hash[pos] = index;
        return 1;
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        cnt += insert(tmp);
    }
    cout << cnt << endl;
    return 0;
}

Suffix Array

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 1000000
using namespace std;
int n;    char ch[MAX_N+5];
int s[MAX_N+5], sa[MAX_N+5], tx[MAX_N+5], ty[MAX_N+5], cnt[MAX_N+5], rank[MAX_N+5];
int trans(char c) {
    if (c >= '0' && c <= '9')	return c-'0'+1;
    if (c >= 'A' && c <= 'Z')	return c-'A'+11;
    if (c >= 'a' && c <= 'z')	return c-'a'+37;
}
void getSA() {
    int *x = tx, *y = ty;	int DICNUM = 63;
    for (int i = 1; i <= n; i++)	cnt[x[i] = s[i]]++;
    for (int i = 2; i <= DICNUM; i++)	cnt[i] += cnt[i-1];
    for (int i = n; i; i--)	sa[cnt[x[i]]--] = i;
    for (int h = 1; h <= n; h <<= 1) {
        int c = 0;
        for (int i = n-h+1; i <= n; i++)	y[++c] = i;
        for (int i = 1; i <= n; i++)	if (sa[i] > h)	y[++c] = sa[i]-h;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)	cnt[x[i]]++;
        for (int i = 2; i <= DICNUM; i++)	cnt[i] += cnt[i-1];
        for (int i = n; i; i--)	sa[cnt[x[y[i]]]--] = y[i];
        swap(x, y), c = 0, x[sa[1]] = ++c;
        for (int i = 2; i <= n; i++)	x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+h] == y[sa[i-1]+h]) ? c : ++c;
        DICNUM = c;	if (c == n)	break;
    }
}
int main() {
    scanf("%s", ch);	n = strlen(ch);
    for (int i = 0; i < n; i++)	s[i+1] = trans(ch[i]);
    getSA();
    printf("%d", sa[1]);	for (int i = 2; i <= n; i++)	printf(" %d", sa[i]);
    return 0;
}

Suffix Automaton

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_N 1000000
using namespace std;
typedef long long lnt;
struct node {int ch[26], par, len;} SAM[MAX_N*2+500];
int sz, root, last, cnt[MAX_N*2+500], dfn[MAX_N*2+500], f[MAX_N*2+500];
int newnode(int _len) {SAM[++sz].len = _len;    return sz;}
void init() {sz = 0, root = last = newnode(0);}
void extend(int c) {
    int p = last, np = newnode(SAM[p].len+1);	last = np, f[np] = 1;
    for (; p && !SAM[p].ch[c]; p = SAM[p].par)	SAM[p].ch[c] = np;
    if (!p)	SAM[np].par = root;
    else {
        int q = SAM[p].ch[c];
        if (SAM[q].len == SAM[p].len+1)	SAM[np].par = q;
        else {
            int nq = newnode(SAM[p].len+1);
            memcpy(SAM[nq].ch, SAM[q].ch, sizeof(SAM[q].ch));
            SAM[nq].par = SAM[q].par, SAM[q].par = SAM[np].par = nq;
            for (; p && SAM[p].ch[c] == q; p = SAM[p].par)	SAM[p].ch[c] = nq;
        }
    }
}
int main() {
    char s[MAX_N+5];	init(), scanf("%s", s);	int l = strlen(s);
    for (int i = 0; i < l; i++)	extend(s[i]-'a');
    for (int i = 1; i <= sz; i++)	cnt[SAM[i].len]++;
    for (int i = 1; i <= l; i++)	cnt[i] += cnt[i-1];
    for (int i = 1; i <= sz; i++)	dfn[cnt[SAM[i].len]--] = i;
    lnt ans = 0;
    for (int i = sz; i >= 1; i--) {
        int p = dfn[i];	f[SAM[p].par] += f[p];
        if (f[p] > 1)	ans = max(ans, (lnt)f[p]*SAM[p].len);
    }
    printf("%lld", ans);
    return 0;
}