Al-Azhar University

4.13 Segmented sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

ICPC Team Reference Material 4.14 The stable marriage problem . . . . . . . . . . . . . . . . . . . . . . . . . . 21

5 String processing 21
Contents 5.1
5.2
Trie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Knuth Morris Pratt (kmp) . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
22

1 Setup 1 6 Geometry 22
1.1 Vimrc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 6.1 Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.2 Capslock as escape. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
7 More advanced topics 23
7.1 A* algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Graph algorithms 2 7.2 Mo’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1 Adjacency list representation . . . . . . . . . . . . . . . . . . . . . . . . . . 2 7.3 Square root decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 Articulation points and bridges . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Bellman ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.4 Bi-connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
8 Miscellaneous 24
2.5 Bi-partite graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
8.1 C++ template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.6 Breadth first search (bfs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

8.2 Double comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Fast input/output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 25
2.7 4
2.8 Cycle detection (directed graph) . . . . . . . . . . . . . . . . . . . . . . . . . 4
8.4 Gcd & Lcm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Modular calculations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.9 Cycle detection (undirected graph) . . . . . . . . . . . . . . . . . . . . . . . . 4
8.5 25

2.10 Depth first search (dfs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

8.6 Debugging tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Overloaded operators to accept 128 bit integer . . . . . . . . . . . . . . . . . . . .
Dijkstra (dense graph) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.7 26
2.11 5
Policy based data structures . . . . . . . . . . . . . . . . . . . . . . . . . . .
Dijkstra (grid) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.8 26
2.12 5
Pseudo random number generator . . . . . . . . . . . . . . . . . . . . . . . . .
2.13 Dijkstra (negative weighted graph) . . . . . . . . . . . . . . . . . . . . . . . . 5
8.9 26
Stress test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Dijkstra (sparse graph) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.10 26
2.14 5
2.15 Directed cyclic graph into acyclic . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.16 Edge classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Eulerian tour tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.17
2.18 Flood fill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
7 1 Setup
2.19 Floyd warshall (all pairs shortest path) . . . . . . . . . . . . . . . . . . . . . . 7
2.20 Minimum spanning tree (kruskal) . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.21 Kth ancestor and lowest common ancestor (binary lifting) . . . . . . . . . . . . . . . 8 1.1 Vimrc
2.22 Lowest common ancestor (euler tour) . . . . . . . . . . . . . . . . . . . . . . . 9
2.23 Minimum vertex cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.24 Restoring the path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1 let mapleader = "\"
2.25 Shortest path faster algorithml (spfa) . . . . . . . . . . . . . . . . . . . . . . . 10 2 syntax on
2.26 Single source shortest path . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3
4
filetype plugin on
set nocompatible
2.27 Single source shortest path (grid) . . . . . . . . . . . . . . . . . . . . . . . . . 11 5 set autoread
2.28 Tarjan (strongly connected components) . . . . . . . . . . . . . . . . . . . . . . 11 6 set foldmethod=marker
2.29 Topological sort (dfs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7 set autoindent
2.30 Topological sort (kahns algorithm) . . . . . . . . . . . . . . . . . . . . . . . . 11
8
9
set clipboard+=unnamedplus
set number relativenumber
2.31 Tree diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 10 set shiftwidth=2 softtabstop=2 expandtab
2.32 0-1 bfs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 11 map <leader>c :w! && !compile %:p:r<CR>
2.33 0-1 bfs (grid) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 12
13
vmap < <gv
vmap > >gv

3 Data structures 13
3.1 Union find disjoint sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2 Segment tree (rmq) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Capslock as escape
3.3 Merge sort tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4 Sparse table (rmq) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.5 Sparse table (rsq) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1 setxkbmap -layout us
3.6 Merge sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 xmodmap -e ’clear Lock’
3.7 Selection sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 xmodmap -e ’keycode 66 = Escape’
3.8 Bubble sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4 Mathematics 16
4.1 Euler totient function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Compilation
4.2 Euler phi (sieve) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Extended wheel factorization . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Least prime factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1 #!/bin/bash
4.5 Miller rabin test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 # put this file in .local/bin or add its dir to the PATH variable
4.6 Mobius function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3
4
compile() {
g++ -Wall -Wextra -Wshadow -Ofast -std=c++17 -pedantic -Wformat=2 -Wconversion -Wlogical-op -Wshift-
4.7 Mobius (sieve) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 overflow=2 -Wduplicated-cond -Wfloat-equal -fno-sanitize-recover -fstack-protector -fsanitize=
4.8 Phi factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 address,undefined -fmax-errors=2 -o "$1"{,.cpp}
4.9 Pisano periodic sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5 }
6 compile "$1"
4.10 Simple sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.11 wheel sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Linear sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
4.12 21
 Al-Azhar University
2 Graph algorithms 40
41 if(dfs_low[To[i]] > dfs_num[node])
42 bridges[bridgeInx++] = make_pair(node, To[i]);
43 }
2.1 Adjacency list representation 44
45
else if(To[i] != Par[node])
dfs_low[node] = Min(dfs_low[node], dfs_num[To[i]]);
46 }
47 }
1 template <class T> 48
2 class Graph { 49 int main() {
3 public: 50 cin >> n >> m;
4 vector <int> _head, _next, _to; 51 _clear();
5 vector <T> _cost; 52
6 int edge_number; 53 while(m--) {
7 bool isDirected; 54 cin >> u >> v;
8 55 addEdge(u, v);
9 Graph() = default; 56 addEdge(v, u);
10 Graph(int V, int E, bool isDirec) { 57 }
11 isDirected = isDirec; 58
12 _head.assign(V + 9, 0); 59 for(int i = 1; i <= n; ++i)
13 _next.assign(isDirected ? E + 9 : E * 2 + 9, 0); 60 if(dfs_num[i] == 0) {
14 _to.assign(isDirected ? E + 9 : E * 2 + 9, 0); 61 root = i;
15 // _cost.assign(isDirected ? E + 9 : E * 2 + 9, 0); 62 rootChildren = 0;
16 edge_number = 0; 63 Tarjan(i);
17 } 64 Art[root] = (rootChildren > 1);
18 65 }
19 void addEdge(int u, int v, T w = 0) { 66
20 _next[++edge_number] = _head[u]; 67 cout << "Art Points :\n";
21 _to[edge_number] = v; 68 for(int i = 1; i <= n; ++i) if(Art[i])
22 // _cost[edge_number] = w; 69 cout << i << " ";
23 _head[u] = edge_number; 70
24 } 71 cout << "\nBridges :\n";
25 72 for(int i = 0; i < bridgeInx; ++i)
26 void addBiEdge(int u, int v, int w = 0) { 73 cout << bridges[i].first << " - " << bridges[i].second << endl;
27 addEdge(u, v, w); 74 }
28 addEdge(v, u, w);
29 }
30
31 void dfs(int node) {
32
33
vis[node] = true;
for(int i = _head[node]; i; i = _next[i]) if(!vis[_to[i]]) {
2.3 Bellman ford
34 dfs(_to[i]);
35 }
36 } 1 // Bellman-Ford Algorithm
37 }; 2 // In programming contests, the slowness of Bellman Ford and its negative cycle detection feature
3 // causes it to be used only to solve the SSSP problem on small graph
4 // which is not guaranteed to be free from negative weight cycle
5
6 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
2.2 Articulation points and bridges 7
8
ll INF = 0x3f3f3f3f3f3f3f3f;

9 int Head[N], Par[N], Next[M], To[M], Cost[M], ne, n, m, u, v, st, tr, tax;
10 ll dis[N];
1 const int N = 1e5 + 9, M = 2e6 + 9, oo = 0x3f3f3f3f, Mod = 1e9 + 7; 11
2 ll INF = 0x3f3f3f3f3f3f3f3f; 12 void addEdge(int from, int to, int cost) {
3 13 Next[++ne] = Head[from];
4 int Head[N], Next[M], To[M], Cost[M]; 14 Head[from] = ne;
5 int Par[N], dfs_num[N], dfs_low[N]; 15 Cost[ne] = cost;
6 int ne, n, m, u, v, w; 16 To[ne] = to;
7 int root, rootChildren, dfs_timer, bridgeInx; 17 }
8 bool Art[N]; 18
9 vector < pair <int, int> > bridges(M); 19 void _clear() {
10 20 memset(Head, 0, sizeof(Head[0]) * (n + 2));
11 void addEdge(int from, int to, int cost = 0) { 21 ne = 0;
12 Next[++ne] = Head[from]; 22 }
13 Head[from] = ne; 23
14 Cost[ne] = cost; 24 bool hasNC() {
15 To[ne] = to; 25 for(int i = 1; i <= n; ++i)
16 } 26 for(int j = Head[i]; j; j = Next[j])
17 27 if(dis[i] < INF && dis[i] + Cost[j] < dis[To[j]])
18 void _clear() { 28 return true;
19 memset(Head, 0, sizeof(Head[0]) * (n + 2)); 29
20 memset(dfs_num, 0, sizeof(dfs_num[0]) * (n + 2)); 30 return false;
21 memset(Par, -1, sizeof(Par[0]) * (n + 2)); 31 }
22 memset(Art, 0, sizeof(Art[0]) * (n + 2)); 32
23 ne = dfs_timer = bridgeInx = 0; 33 bool Bellman_Ford(int src) {
24 } 34 memset(dis, 0x3f, sizeof(dis[0]) * (n + 2));
25 35 memset(Par, -1, sizeof(Par[0]) * (n + 2));
26 void Tarjan(int node) { 36
27 dfs_num[node] = dfs_low[node] = ++dfs_timer; 37 dis[src] = 0;
28 38 bool newRelaxation = true;
29 for(int i = Head[node]; i; i = Next[i]) { 39
30 if(dfs_num[To[i]] == 0) 40 for(int i = 2; i <= n && newRelaxation; ++i) {
31 { 41 newRelaxation = false;
32 if(node == root) ++rootChildren; 42 for(int i = 1; i <= n; ++i)
33 43 for(int j = Head[i]; j; j = Next[j])
34 Par[To[i]] = node; 44 if(dis[i] < INF && dis[i] + Cost[j] < dis[To[j]]) {
35 Tarjan(To[i]); 45 dis[To[j]] = dis[i] + Cost[j];
36 dfs_low[node] = Min(dfs_low[node], dfs_low[To[i]]); 46 Par[To[j]] = i;
37 47 newRelaxation = true;
38 if(dfs_low[To[i]] >= dfs_num[node]) 48 }

2
39 Art[node] = true; 49 }
 Al-Azhar University
50 return hasNC();
51 }
2.5 Bi-partite graph

2.4 Bi-connected components 1

2
const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
ll INF = 0x3f3f3f3f3f3f3f3f;
3
4 int Head[N], Par[N], Next[M], To[M], Cost[M], ne, n, m, u, v, st, tr, tax;
5 ll dis[N];
1 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f, Mod = 1e9 + 7; 6 bool color[N], vis[N];
2 const ll INF = 0x3f3f3f3f3f3f3f3f; 7
3
8 void addEdge(int from, int to) {
4 int Head[N], Next[M], To[M]; 9 Next[++ne] = Head[from];
5 int Par[N], dfs_num[N], dfs_low[N]; 10 Head[from] = ne;
6 int ne, n, m, u, v; 11 To[ne] = to;
7 int root, rootChildren, dfs_timer; 12 }
8 int Stack[N], top, ID; 13
9 bool Art[N]; 14 bool checkBiPartite(int node, int par = 0) {
10 vector < vector <int> > BiCCs(N), BiCCIDs(N); 15 if(vis[node])
11
16 return color[par] != color[node];
12 void addEdge(int from, int to) { 17
13 Next[++ne] = Head[from]; 18 color[node] = color[par] ˆ 1;
14 Head[from] = ne; 19
15 To[ne] = to; 20 vis[node] = true;
16 } 21 bool ok = true;
17
22 for(int i = Head[node]; i; i = Next[i])
18 void _clear() { 23 if(To[i] != par)
19 memset(Head, 0, sizeof(Head[0]) * (n + 2)); 24 ok &= checkBiPartite(To[i], node);
20 memset(dfs_num, 0, sizeof(dfs_num[0]) * (n + 2)); 25
21 memset(Par, -1, sizeof(Par[0]) * (n + 2)); 26 return ok;
22 memset(Art, 0, sizeof(Art[0]) * (n + 2)); 27 }
23 ne = dfs_timer = top = ID = 0; 28
24 BiCCs = BiCCIDs = vector < vector <int> > (N); 29 int main() {
25 } 30 cin >> n >> m;
26
31 while(m--) {
27 void Tarjan(int node) { 32 cin >> u >> v;
28 dfs_num[node] = dfs_low[node] = ++dfs_timer; 33 addEdge(u, v);
29 Stack[top++] = node; 34 addEdge(v, u);
30
35 }
31 for(int i = Head[node]; i; i = Next[i]) { 36
32 if(dfs_num[To[i]] == 0) { 37 bool isBiPartite = true;
33 if(node == root) ++rootChildren; 38 for(int i = 1; i <= n; ++i) if(!vis[i])
34
39 isBiPartite &= checkBiPartite(i);
35 Par[To[i]] = node; 40
36 Tarjan(To[i]); 41 cout << (isBiPartite ? "YES" : "NO") << endl;
37
42 }
38 dfs_low[node] = Min(dfs_low[node], dfs_low[To[i]]);
39
40 if(dfs_low[To[i]] >= dfs_num[node]) {
41 Art[node] = true;
42
43
++ID;
for(int x = -1; x ˆ To[i];) { 2.6 Breadth first search (bfs)
44 x = Stack[--top];
45 BiCCIDs[x].emplace_back(ID);
46 BiCCs[ID].emplace_back(x);
1 #include <bits/stdc++.h>
47 }
2 using namespace std;
48 BiCCIDs[node].emplace_back(ID);
3 typedef int64_t ll;
49 BiCCs[ID].emplace_back(node);
4
50 }
5 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
51 }
6 ll INF = 0x3f3f3f3f3f3f3f3f;
52 else if(To[i] != Par[node])
7
53 dfs_low[node] = Min(dfs_low[node], dfs_num[To[i]]);
8 int Head[N], Par[N], Next[M], To[M], Cost[M], ne, n, m, u, v, st, tr, tax;
54 }
9 ll dis[N];
55 }
10
56
11 void addEdge(int from, int to, int cost) {
57 int main() {
12 Next[++ne] = Head[from];
58 cin >> n >> m;
13 Head[from] = ne;
59 _clear();
14 Cost[ne] = cost;
60
15 To[ne] = to;
61 while(m--) {
16 }
62 cin >> u >> v;
17
63 addEdge(u, v);
18 void _clear() {
64 addEdge(v, u);
19 memset(Head, 0, sizeof(Head[0]) * (n + 2));
65 }
20 ne = 0;
66
21 }
67 for(int i = 1; i <= n; ++i)
22
68 if(dfs_num[i] == 0) { // O(n + m)
23 void BFS(int src) {
69 root = i;
24 memset(dis, 0x3f, sizeof(dis[0]) * (n + 2));
70 rootChildren = 0;
25 memset(Par, -1, sizeof(Par[0]) * (n + 2));
71 Tarjan(i);
26
72 Art[root] = (rootChildren > 1);
27 queue <int> q;
73 }
28 q.push(src);
74
29 dis[src] = 0;
75 for(int i = 1; i <= ID; ++i) {
30
76 cout << "Component : " << i << " contains : ";
31 int u;
77 for(int j = 0; j < (int)BiCCs[i].size(); ++j)
32 while(q.size()) {
78 cout << BiCCs[i][j] << " \n"[j == BiCCs[i].size() - 1];
33 u = q.front(); q.pop();
79 }
34 for(int i = Head[u]; i; i = Next[i])
80 }
35 if(dis[To[i]] == oo) {

3
36 dis[To[i]] = dis[u] + 1;
 Al-Azhar University
37 Par[To[i]] = u; 28 cin >> n >> m;
38 q.push(To[i]); 29 while(m--) {
39 } 30 cin >> u >> v;
40 } 31 addEdge(u, v);
41 } 32 }
42 33
43 int main() 34 for(int i = 1; i <= n; ++i)
44 { 35 if(!visited[i])
45 cin >> n >> m >> st >> tr; 36 DFS(i);
46 while(m--) { 37
47 cin >> u >> v >> tax; 38 cout << (hasCycle ? "YES" : "NO") << endl;
48 addEdge(u, v, tax); 39 }
49 addEdge(v, u, tax);
50 }
51
52 BFS(st);
53
54 }
cout << dis[tr] << endl; 2.9 Cycle detection (undirected graph)
1 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
2 ll INF = 0x3f3f3f3f3f3f3f3f;
2.7 Connected components 3
4 int Head[N], Par[N], Next[M], To[M], Cost[M], ne, n, m, u, v, st, tr, tax;
5 ll dis[N];
6 bool visited[N], hasCycle;
1 const int N = 1e5 + 9, M = 1e6 + 9; 7
2 8 void addEdge(int from, int to) {
3 int Head[N], Next[M], To[M], ne, u, v, n, m, CCs; 9 Next[++ne] = Head[from];
4 bool visited[N]; 10 Head[from] = ne;
5 11 To[ne] = to;
6 void addEdge(int from, int to) { 12 }
7 Next[++ne] = Head[from]; 13
8 Head[from] = ne; 14 void DFS(int node, int parent = -1) {
9 To[ne] = to; 15 if(hasCycle |= visited[node])
10 } 16 return;
11 17 visited[node] = true;
12 void DFS(int node) { 18
13 visited[node] = true; 19 for(int i = Head[node]; i; i = Next[i])
14 for(int e = Head[node]; e; e = Next[e]) 20 if(To[i] != parent)
15 if(!visited[To[e]]) 21 DFS(To[i], node);
16 DFS(To[e]); 22 }
17 } 23
18 24 int main() {
19 int main() { 25 cin >> n >> m;
20 cin >> n >> m; 26 while(m--) {
21 while(m--) { 27 cin >> u >> v;
22 cin >> u >> v; 28 addEdge(u, v);
23 addEdge(u, v); 29 addEdge(v, u);
24 addEdge(v, u); 30 }
25 } 31
26 32 for(int i = 1; i <= n; ++i)
27 for(int node = 1; node <= n; ++node) if(!visited[node]) 33 if(!visited[i])
28 ++CCs, DFS(node); 34 DFS(i);
29 35
30 cout << CCs << endl; 36 cout << (hasCycle ? "YES" : "NO") << endl;
31 } 37 }

2.8 Cycle detection (directed graph) 2.10 Depth first search (dfs)
1 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f; 1 #include <bits/stdc++.h>
2 ll INF = 0x3f3f3f3f3f3f3f3f; 2 using namespace std;
3 3 typedef int64_t ll;
4 int Head[N], Par[N], Next[M], To[M], Cost[M], ne, n, m, u, v, st, tr, tax; 4
5 ll dis[N]; 5 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
6 bool hasCycle; 6 ll INF = 0x3f3f3f3f3f3f3f3f;
7 char visited[N]; 7
8 8 int Head[N], Par[N], Next[M], To[M], Cost[M], ne, n, m, u, v, st, tr, tax;
9 void addEdge(int from, int to) { 9 ll dis[N];
10 Next[++ne] = Head[from]; 10 bool vis[N];
11 Head[from] = ne; 11
12 To[ne] = to; 12 void addEdge(int from, int to, int cost) {
13 } 13 Next[++ne] = Head[from];
14 14 Head[from] = ne;
15 void DFS(int node) { 15 Cost[ne] = cost;
16 if(hasCycle |= visited[node] == 1) 16 To[ne] = to;
17 return; /** Oops, revisiting active node **/ 17 }
18 visited[node] = 1; /** current node legend mode has been activated **/ 18
19 19 void _clear() {
20 for(int i = Head[node]; i; i = Next[i]) 20 memset(Head, 0, sizeof(Head[0]) * (n + 2));
21 if(visited[To[i]] != 2) 21 ne = 0;
22 DFS(To[i]); 22 }
23 23
24 visited[node] = 2; /** done with this node and mark it as visited **/ 24 void DFS(int node) {
25 } 25 vis[node] = true;
26 26 for(int i = Head[node]; i; i = Next[i])

4
27 int main() { 27 if(!vis[To[i]])
 Al-Azhar University
28 DFS(To[i]); 17
29 } 18 dis[sr][sc] = grid[sr][sc];
30 19 Q.push({-grid[sr][sc], sr, sc});
31 int main() { 20
32 cin >> n >> m; 21 int cost, r, c, nr, nc;
33 while(m--) { 22 while(Q.size()) {
34 cin >> u >> v; 23 tie(cost, r, c) = Q.top(); Q.pop();
35 addEdge(u, v); 24 if((-cost) > dis[r][c]) continue; // lazy deletion
36 addEdge(v, u); 25
37 } 26 for(int i = 0; i < 4; ++i) {
38 27 nr = r + dr[i];
39 for(int i = 1; i <= n; ++i) 28 nc = c + dc[i];
40 if(!vis[i]) 29
41 DFS(i); 30 if(!valid(nr, nc)) continue;
42 } 31
32 if(dis[r][c] + grid[nr][nc] < dis[nr][nc]) {
33 dis[nr][nc] = dis[r][c] + grid[nr][nc];
34 Q.push({-dis[nr][nc], nr, nc});
35 }
2.11 Dijkstra (dense graph) 36
37 }
}

38 }

1 /** Dijkstra on dense graphs

2 complexity : O(nˆ2 + m)
3 **/
4
5 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
2.13 Dijkstra (negative weighted graph)
6 ll INF = 0x3f3f3f3f3f3f3f3f;
7
8 int Head[N], Par[N], Next[M], To[M], Cost[M], ne, n, m, u, v, st, tr, tax; 1 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
9 ll dis[N]; 2 ll INF = 0x3f3f3f3f3f3f3f3f;
10 3
11 void addEdge(int from, int to, int cost) { 4 int Head[N], Par[N], Next[M], To[M], Cost[M], ne, n, m, u, v, st, tr, tax;
12 Next[++ne] = Head[from]; 5 ll dis[N];
13 Head[from] = ne; 6
14 Cost[ne] = cost; 7 void addEdge(int from, int to, int cost) {
15 To[ne] = to; 8 Next[++ne] = Head[from];
16 } 9 Head[from] = ne;
17 10 Cost[ne] = cost;
18 void _clear() { 11 To[ne] = to;
19 memset(Head, 0, sizeof(Head[0]) * (n + 2)); 12 }
20 ne = 0; 13
21 } 14 void _clear() {
22 15 memset(Head, 0, sizeof(Head[0]) * (n + 2));
23 void Dijkstra(int src, int V) { 16 ne = 0;
24 memset(dis, 0x3f, sizeof(dis[0]) * (n + 2)); 17 }
25 memset(Par, -1, sizeof(Par[0]) * (n + 2)); 18
26 19 void Dijkstra(int src) {
27 vector <bool> mark(V + 1, false); 20 memset(dis, 0x3f, sizeof(dis[0]) * (n + 2));
28 21 memset(Par, -1, sizeof(Par[0]) * (n + 2));
29 dis[src] = 0; 22
30 for(int i = 1; i <= V; ++i) { 23 priority_queue <pair <ll, int> > Q;
31 int node = 0; 24
32 for(int j = 1; j <= V; ++j) 25 dis[src] = 0;
33 if(!mark[j] && dis[j] < dis[node]) 26 Q.push({-dis[src], src});
34 node = j; 27
35 28 int node;
36 if(dis[node] == INF) break; 29 ll cost;
37 30 while(Q.size()) {
38 mark[node] = true; 31 tie(cost, node) = Q.top(); Q.pop();
39 for(int i = Head[node]; i; i = Next[i]) 32 if((-cost) > dis[node]) continue;
40 if(dis[node] + Cost[i] < dis[To[i]]) { 33
41 dis[To[i]] = dis[node] + Cost[i]; 34 for(int i = Head[node]; i; i = Next[i])
42 Par[To[i]] = node; 35 if(dis[node] + Cost[i] < dis[To[i]]) {
43 } 36 dis[To[i]] = dis[node] + Cost[i];
44 } 37 Q.push({-dis[To[i]], To[i]});
45 } 38 Par[To[i]] = node;
39 }
40 }
41 }

2.12 Dijkstra (grid)

1 const int dr[] = { 1, -1, 0, 0, 1, 1, -1, -1 };
2.14 Dijkstra (sparse graph)
2 const int dc[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
3 const char dir[] = {’D’, ’U’, ’R’, ’L’};
4 1 /** Dijkstra on sparse graphs
5 const int N = 1e3 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f; 2 - complexity : O(n + m)logn -> O(nlogn + m)
6 3 - Single Source Single Destination Shortest Path Problem
7 int grid[N][N], dis[N][N], n, m; 4 - Positive Weight Edges only
8 5 * Subpaths of shortest paths from u to v are shortest paths!
9 bool valid(int r, int c) { 6 **/
10 return r >= 1 && r <= n && c >= 1 && c <= m; 7
11 } 8 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
12 9 ll INF = 0x3f3f3f3f3f3f3f3f;
13 void Dijkstra(int sr, int sc) { 10
14 memset(dis, 0x3f, sizeof (dis)); // memset(dis, 0x3f, n * m) we don’t do that here 11 int Head[N], Par[N], Next[M], To[M], Cost[M], ne, n, m, u, v, st, tr, tax;
15 12 ll dis[N];

5
16 priority_queue <tuple <int, int, int> > Q; 13
 Al-Azhar University
14 void addEdge(int from, int to, int cost) { 48 }
15 Next[++ne] = Head[from]; 49
16 Head[from] = ne; 50 if(dfs_num[node] == dfs_low[node]) {
17 Cost[ne] = cost; 51 ++ID;
18 To[ne] = to; 52 for(int cur = -1; cur ˆ node;) {
19 } 53 in_stack[cur = Stack[--top]] = false;
20 54 compID[cur] = ID;
21 void _clear() { 55 ++compSize[ID];
22 memset(Head, 0, sizeof(Head[0]) * (n + 2)); 56 }
23 ne = 0; 57 }
24 } 58 }
25 59
26 void Dijkstra(int src, int trg) { 60 void Tarjan() {
27 memset(dis, 0x3f, sizeof(dis[0]) * (n + 2)); 61 for(int i = 1; i <= n; ++i)
28 memset(Par, -1, sizeof(Par[0]) * (n + 2)); 62 if(dfs_num[i] == 0)
29 63 Tarjan(i);
30 priority_queue <pair <ll, int> > Q; 64 }
31 65
32 dis[src] = 0; 66 void DFS(int node) {
33 Q.push({-dis[src], src}); 67 dfs_num[node] = 1;
34 68 for(int i = Head[node]; i; i = Next[i]) {
35 int node; 69 if(compID[node] != compID[To[i]])
36 ll cost; 70 addEdgeDAG(compID[node], compID[To[i]]);
37 while(Q.size()) { 71
38 tie(cost, node) = Q.top(); Q.pop(); 72 if(dfs_num[To[i]] == 0)
39 73 DFS(To[i]);
40 if((-cost) > dis[node]) continue; // lazy deletion 74 }
41 if(node == trg) return; // cheapest cost in case of positive weight edges 75 }
42 76
43 for(int i = Head[node]; i; i = Next[i]) 77 void construct_dag() {
44 if(dis[node] + Cost[i] < dis[To[i]]) { 78 memset(dfs_num, 0, sizeof(dfs_num[0]) * (n + 2));
45 dis[To[i]] = dis[node] + Cost[i]; 79
46 Q.push({-dis[To[i]], To[i]}); 80 for(int i = 1; i <= n; ++i)
47 Par[To[i]] = node; 81 if(dfs_num[i] == 0)
48 } 82 DFS(i);
49 } 83 }
50 }

2.16 Edge classification

2.15 Directed cyclic graph into acyclic
1 #pragma GCC optimize ("Ofast")
1 const int N = 1e5 + 9, M = 2e6 + 9, oo = 0x3f3f3f3f, Mod = 1e9 + 7; 2
2 ll INF = 0x3f3f3f3f3f3f3f3f; 3 #include <bits/stdc++.h>
3 4
4 int Head[N], To[M], Next[M], Cost[M]; 5 #define UNVISITED 0
5 int dfs_num[N], dfs_low[N], out[N]; 6 #define EXPLORED 1
6 int Stack[N], compID[N], compSize[N]; 7 #define VISITED 2
7 int ne, n, m, u, v, w; 8
8 int dfs_timer, top, ID; 9 using namespace std;
9 bool in_stack[N]; 10
10 11 typedef int64_t ll;
11 int HeadDAG[N], ToDAG[M], NextDAG[M], CostDAG[M], neDAG; 12
12 13 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
13 void addEdge(int from, int to, int cost = 0) { 14 ll INF = 0x3f3f3f3f3f3f3f3f;
14 Next[++ne] = Head[from]; 15
15 Head[from] = ne; 16 int Head[N], Next[M], To[M], Par[N], in_time[N], ne, n, m, u, v, dfs_timer;
16 Cost[ne] = cost; 17 char dfs_num[N];
17 To[ne] = to; 18
18 } 19 void addEdge(int from, int to) {
19 20 Next[++ne] = Head[from];
20 void addEdgeDAG(int from, int to, int cost = 0) { 21 Head[from] = ne;
21 NextDAG[++neDAG] = HeadDAG[from]; 22 To[ne] = to;
22 HeadDAG[from] = neDAG; 23 }
23 CostDAG[ne] = cost; 24
24 ToDAG[neDAG] = to; 25 void edgeClassification(int node) {
25 ++out[from]; 26 dfs_num[node] = EXPLORED;
26 } 27 in_time[node] = ++dfs_timer;
27 28
28 void _clear() { 29 for(int i = Head[node]; i; i = Next[i]) {
29 memset(Head, 0, sizeof(Head[0]) * (n + 2)); 30 if(dfs_num[To[i]] == UNVISITED) {
30 memset(dfs_num, 0, sizeof(dfs_num[0]) * (n + 2)); 31 cout << "Tree Edge : " << node << " -> " << To[i] << endl;
31 memset(compID, 0, sizeof(compID[0]) * (n + 2)); 32
32 memset(compSize, 0, sizeof(compSize[0]) * (n + 2)); 33 Par[To[i]] = node;
33 memset(HeadDAG, 0, sizeof(HeadDAG[0]) * (n + 2)); 34 edgeClassification(To[i]);
34 memset(out, 0, sizeof(out[0]) * (n + 2)); 35 }
35 ne = dfs_timer = top = neDAG = ID = 0; 36 else if(dfs_num[To[i]] == VISITED) {
36 } 37 /** Cross Edges only occur in directed graph */
37 38 if(in_time[To[i]] < in_time[node])
38 void Tarjan(int node) { 39 cout << "Cross Edge : " << node << " -> " << To[i] << endl;
39 dfs_num[node] = dfs_low[node] = ++dfs_timer; 40 else
40 in_stack[Stack[top++] = node] = true; 41 cout << "Forward Edge : " << node << " -> " << To[i] << endl;
41 42 }
42 for(int i = Head[node]; i; i = Next[i]) { 43 else if(dfs_num[To[i]] == EXPLORED) {
43 if(dfs_num[To[i]] == 0) 44 if(Par[node] == To[i])
44 Tarjan(To[i]); 45 cout << "Bi-Directional Edge : " << node << " -> " << To[i] << endl;
45 46 else
46 if(in_stack[To[i]]) 47 cout << "Backward Edge : " << node << " -> " << To[i] << " (Cycle)" << endl;

6
47 dfs_low[node] = Min(dfs_low[node], dfs_low[To[i]]); 48 }
 Al-Azhar University
49 } 2.18 Flood fill
50
51 dfs_num[node] = VISITED;
52 }
1 /** check if there is a path from (0, 0) to (n - 1, m - 1) using ’.’ only **/
53
2
54 int main() {
3 int dr[4] = {1, -1, 0, 0};
55 cin >> n >> m;
4 int dc[4] = {0, 0, 1, -1};
56 while(m--) {
5 char grid[N][M];
57 cin >> u >> v;
6 int n, m;
58 addEdge(u, v);
7
59 }
8 bool valid(int r, int c) {
60
9 return r >= 0 && r < n && c >= 0 && c < m && grid[r][c] == ’.’;
61 for(int i = 1; i <= n; ++i)
10 }
62 if(!dfs_num[i])
11
63 edgeClassification(i);
12 bool isDis(int r, int c) {
64 }
13 return r == n - 1 && c == m - 1;
14 }
15
16 bool FloodFill(int r, int c) {
17 if(!valid(r, c)) return false;
2.17 Eulerian tour tree 18 if(isDis(r, c)) return true;
19
20 grid[r][c] = ’#’;
21 for(int i = 0; i < 4; ++i)
1 int Head[N], To[M], Next[M], Cost[M]; 22 if(FloodFill(r + dr[i], c + dc[i]))
2 int ne, n, m, u, v, w; 23 return true;
3
24 return false;
4 int Last[N], First[N], euler_tour[1 + N << 1]; 25 }
5 ll Height[1 + N << 1]; 26
6 int euler_timer; 27 int main() {
7
28 cin >> n >> m;
8 void addEdge(int from, int to, int cost = 0) { 29 for(int i = 0; i < n; ++i)
9 Next[++ne] = Head[from]; 30 for(int j = 0; j < m; ++j)
10 Head[from] = ne; 31 cin >> grid[i][j];
11 Cost[ne] = cost; 32
12 To[ne] = to; 33 cout << (FloodFill(0, 0) ? "YES" : "NO") << endl;
13 } 34 }
14
15 void _clear() {
16 memset(Head, 0, sizeof(Head[0]) * (n + 2));
17 memset(Last, 0, sizeof(Last[0]) * (n + 2));
18
19
memset(First,
ne = euler_timer =
0, sizeof(First[0])
0;
* (n + 2)); 2.19 Floyd warshall (all pairs shortest path)
20 }
21
22 /** 1 /** -The graph has a ’negative cycle’ if at the end of the algorithm,
23 euler_tour[1 .. n * 2 - 1] = which records the sequence of visited nodes 2 the distance from a vertex v to itself is negative.
24 Height[1 .. n * 2 - 1] = which records the depth of each visited node 3
25 4 - before k-th phase the value of d[i][j] is equal to the length of
26 First[1 .. n] = records the index of the first occurrence of node i in euler_tour 5 the shortest path from vertex i to the vertex j,
27 Last[1 .. n] = records the index of the last occurrence of node i in euler_tour 6 if this path is allowed to enter only the vertex with numbers smaller than k
28 **/ 7 (the beginning and end of the path are not restricted by this property).
29 8 **/
30 void EulerianTour(int node, ll depth = 0) { 9
31 euler_tour[++euler_timer] = node; 10 const int N = 500 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
32 Height[euler_timer] = depth; 11 const i64 INF = 0x3f3f3f3f3f3f3f3f;
33 First[node] = euler_timer; 12
34 13 int Par[N][N], n, m, u, v, tax;
35 for(int i = Head[node]; i; i = Next[i]) 14 i64 adj[N][N], dis[N][N];
36 if(First[To[i]] == 0) { 15
37 EulerianTour(To[i], depth + Cost[i]); 16 vector <int> restorePath(int st, int tr) {
38 17 vector <int> path;
39 euler_tour[++euler_timer] = node; 18 if(dis[st][tr] == INF) return path;
40 Height[euler_timer] = depth; 19
41 } 20 for(int i = tr; st ˆ i; i = Par[st][i])
42 21 path.push_back(i);
43 Last[node] = euler_timer; 22
44 } 23 path.push_back(st);
45 24 reverse(path.begin(), path.end());
46 void show() { 25 return path;
47 for(int i = 1; i < (n << 1); ++i) cout << euler_tour[i] << " ";cout << endl; 26 }
48 for(int i = 1; i < (n << 1); ++i) cout << Height[i] << " "; cout << endl; 27
49 for(int i = 1; i <= n; ++i) cout << First[i] << " "; cout << endl; 28 void Floyd_Warshall() {
50 for(int i = 1; i <= n; ++i) cout << Last[i] << " "; cout << endl; 29 for(int i = 1; i <= n; ++i)
51 } 30 for(int j = 1; j <= n; ++j)
52 31 Par[i][j] = i;
53 int main() { 32
54 cin >> n >> m; 33 for(int k = 1; k <= n; ++k)
55 _clear(); 34 for(int i = 1; i <= n; ++i)
56 35 for(int j = 1; j <= n; ++j)
57 while(m--) { 36 if(dis[i][k] + dis[k][j] < dis[i][j]) {
58 cin >> u >> v >> w; 37 dis[i][j] = dis[i][k] + dis[k][j];
59 addEdge(u, v, w); 38 Par[i][j] = Par[k][j];
60 addEdge(v, u, w); 39 }
61 } 40 }
62
63 EulerianTour(1);
64 show();
65 }
2.20 Minimum spanning tree (kruskal)

7
 Al-Azhar University
1 class UnionFind { 93 }
2 vector <int> par; 94 }
3 vector <int> siz; 95
4 int num_sets; 96 if(mstEdges.size() == n - 1)
5 size_t sz; 97 return make_pair(minWieght, mstEdges);
6 98
7 public: 99 return make_pair(-1, vector < pair <int, int> > ());
8 UnionFind() : par(1, -1), siz(1, 1), num_sets(0), sz(0) {} 100 }
9 UnionFind(int n) : par(n + 1, -1), siz(n + 1, 1), num_sets(n), sz(n) {}
10
11 int find_set(int u) {
12 assert(u <= sz);
13
14 int leader;
2.21 Kth ancestor and lowest common ancestor (binary lift-
15
16
for(leader = u; ˜par[leader]; leader = par[leader]);
ing)
17 for(int next = par[u]; u != leader; next = par[next]) {
18 par[u] = leader;
19 u = next; 1 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f, Mod = 1e9 + 7;
20 } 2 const int LOG = 20;
21 return leader; 3
22 } 4 int Head[N], To[M], Next[M], Par[N];
23 5 int up[N][LOG + 1];
24 bool same_set(int u, int v) { 6 int Log[N], Level[N];
25 return find_set(u) == find_set(v); 7 int ne, n, u, v, q;
26 } 8
27 9 void addEdge(int from, int to) {
28 bool union_set(int u, int v) { 10 Next[++ne] = Head[from];
29 if(same_set(u, v)) return false; 11 Head[from] = ne;
30 12 To[ne] = to;
31 int x = find_set(u); 13 }
32 int y = find_set(v); 14
33 15 void _clear() {
34 if(siz[x] < siz[y]) swap(x, y); 16 memset(Head, 0, sizeof(Head[0]) * (n + 2));
35 17 memset(Par, 0, sizeof(Par[0]) * (n + 2));
36 par[y] = x; 18 memset(Level, 0, sizeof(Level[0]) * (n + 2));
37 siz[x] += siz[y]; 19 ne = 0;
38 20 }
39 --num_sets; 21
40 return true; 22 int lastBit(int a) {
41 } 23 return (a & -a);
42 24 }
43 int number_of_sets() { 25
44 return num_sets; 26 void logCalc() {
45 } 27 Log[1] = 0;
46 28 for(int i = 2; i < N; ++i)
47 int size_of_set(int u) { 29 Log[i] = Log[i >> 1] + 1;
48 return siz[find_set(u)]; 30 }
49 } 31
50 32 void DFS(int node, int depth = 0) {
51 size_t size() { 33 Level[node] = depth;
52 return sz; 34 up[node][0] = Par[node]; // Par[root] = root
53 } 35
54 36 for(int i = 1; i <= LOG; ++i) {
55 void clear() { 37 up[node][i] = up[up[node][i - 1]][i - 1];
56 par.clear(); 38 }
57 siz.clear(); 39
58 sz = num_sets = 0; 40 for(int i = Head[node]; i; i = Next[i])
59 } 41 if(To[i] != Par[node]) {
60 42 Par[To[i]] = node;
61 void assign(size_t n) { 43 DFS(To[i], depth + 1);
62 par.assign(n + 1, -1); 44 }
63 siz.assign(n + 1, 1); 45 }
64 sz = num_sets = n; 46
65 } 47 int KthAncestor(int u, int k) {
66 48 if(k > Level[u]) return -1;
67 map < int, vector <int> > groups(int st) { 49
68 map < int, vector <int> > ret; 50 for(int i = lastBit(k); k; k -= lastBit(k), i = lastBit(k))
69 51 u = up[u][Log[i]];
70 for(size_t i = st; i < sz + st; ++i) 52
71 ret[find_set(i)].push_back(i); 53 return u;
72 54 }
73 return ret; 55
74 } 56 int LCA(int u, int v) {
75 }; 57 if(Level[u] < Level[v]) swap(u, v);
76 58 int k = Level[u] - Level[v];
77 int n, m, u, v, w; 59
78 vector < tuple <int, int, int> > edges; 60 u = KthAncestor(u, k);
79 UnionFind uf; 61 if(u == v) return u;
80 62
81 pair < ll, vector < pair <int, int> > > Kruskal() { 63 for(int i = LOG; i >= 0; --i)
82 sort(edges.begin(), edges.end()); 64 if(up[u][i] ˆ up[v][i])
83 65 {
84 vector < pair <int, int> > mstEdges; 66 u = up[u][i];
85 int from, to, cost; 67 v = up[v][i];
86 ll minWieght = 0; 68 }
87 69
88 for(tuple <int, int, int> edge : edges) { 70 return up[u][0];
89 tie(cost, from, to) = edge; 71 }
90 if(uf.union_set(from, to)) { 72
91 minWieght += cost; 73 int main() {

8
92 mstEdges.push_back(make_pair(from, to)); 74 cin >> n;
 Al-Azhar University
75 _clear(); 65 int Height[N << 1];
76 66 int euler_timer;
77 for(int i = 1; i < n; ++i) { 67
78 cin >> u >> v; 68 void addEdge(int from, int to, int cost = 1) {
79 addEdge(u, v); 69 Next[++ne] = Head[from];
80 addEdge(v, u); 70 Head[from] = ne;
81 } 71 Cost[ne] = cost;
82 72 To[ne] = to;
83 logCalc(); 73 }
84 for(int i = 1; i <= n; ++i) if(Par[i] == 0) { 74
85 Par[i] = i; 75 void _clear() {
86 DFS(i); 76 memset(Head, 0, sizeof(Head[0]) * (n + 2));
87 } 77 memset(Last, 0, sizeof(Last[0]) * (n + 2));
88 78 memset(First, 0, sizeof(First[0]) * (n + 2));
89 cin >> q; 79 ne = euler_timer = 0;
90 while(q--) { 80 }
91 cin >> u >> v; 81
92 cout << LCA(u, v) << endl; 82 void EulerianTour(int node, int depth = 0) {
93 } 83 euler_tour[++euler_timer] = node;
94 } 84 Height[euler_timer] = depth;
85 First[node] = euler_timer;
86
87 for(int i = Head[node]; i; i = Next[i])
88 if(First[To[i]] == 0) {
2.22 Lowest common ancestor (euler tour) 89
90
EulerianTour(To[i], depth + Cost[i]);

91 euler_tour[++euler_timer] = node;
92 Height[euler_timer] = depth;
1 template <class T, class F = function <T(const T&, const T&)> > 93 }
2 class SparseTable { 94
3 int _N; 95 Last[node] = euler_timer;
4 int _LOG; 96 }
5 vector <T> _A; 97
6 vector < vector <T> > ST; 98 int main() {
7 vector <int> Log; 99 cin >> n >> m;
8 F func; 100 _clear();
9 101
10 public : 102 while(m--) {
11 SparseTable() = default; 103 cin >> u >> v;
12 104 addEdge(u, v);
13 template <class iter> 105 addEdge(v, u);
14 SparseTable(iter _begin, iter _end, const F _func = less <T>()) : func(_func) { 106 }
15 _N = distance(_begin, _end); 107
16 Log.assign(_N + 1, 0); 108 EulerianTour(1);
17 for(int i = 2; i <= _N; ++i) 109
18 Log[i] = Log[i >> 1] + 1; 110 SparseTable <int> st(Height + 1, Height + euler_timer + 1, [&](int a, int b) { return a <= b; });
19 111
20 _LOG = Log[_N]; 112 int l, r; cin >> q;
21 113 while(q--) {
22 _A.assign(_N + 1, 0); 114 cin >> l >> r;
23 ST.assign(_N + 1, vector <T> (_LOG + 1, 0)); 115
24 116 int left = Last[l];
25 __typeof(_begin) i = _begin; 117 int right = Last[r];
26 for(int j = 1; i != _end; ++i, ++j) 118 if(left > right) swap(left, right);
27 _A[j] = *i; 119
28 120 cout << euler_tour[ st.query(left, right) ] << endl;
29 build(); 121 }
30 } 122 }
31
32 void build() {
33 for(int i = 1; i <= _N; ++i)
34 ST[i][0] = i;
35
36 for(int j = 1, k, d; j <= _LOG; ++j) {
2.23 Minimum vertex cover
37 k = (1 << j);
38 d = (k >> 1);
39 1 const int N = 1e5 + 9;
40 for(int i = 1; i + k - 1 <= _N; ++i) { 2
41 T const & x = ST[i][j - 1]; 3 int Head[N], Next[N << 1], To[N << 1], ne, u, v, n, MVC;
42 T const & y = ST[i + d][j - 1]; 4
43 5 void addEdge(int from, int to) {
44 ST[i][j] = func(_A[x], _A[y]) ? x : y; 6 Next[++ne] = Head[from];
45 } 7 Head[from] = ne;
46 } 8 To[ne] = to;
47 } 9 }
48 10
49 T query(int l, int r) { 11 bool DFS(int node, int par = -1) {
50 int d = r - l + 1; 12 bool black = false;
51 T const & x = ST[l][Log[d]]; 13 for(int e = Head[node]; e; e = Next[e])
52 T const & y = ST[l + d - (1 << Log[d])][Log[d]]; 14 if(To[e] != par)
53 15 black |= DFS(To[e], node);
54 return func(_A[x], _A[y]) ? x : y; 16
55 } 17 MVC += black;
56 }; 18 return !black;
57 19 }
58 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f, Mod = 1e9 + 7; 20
59 const ll INF = 0x3f3f3f3f3f3f3f3f; 21 int main() {
60 22 cin >> n;
61 int Head[N], To[M], Next[M], Cost[M]; 23 while(--n) {
62 int ne, n, m, u, v, w, q; 24 cin >> u >> v;
63 25 addEdge(u, v);

9
64 int Last[N], First[N], euler_tour[N << 1]; 26 addEdge(v, u);
 Al-Azhar University
27 } 3 - The maximum k can be V (which is the same as the time complexity of Bellman Fords).
28 4 - However, in practice SPFA (which uses a queue) is as fast as Dijkstras (which uses a priority
29 DFS(1); queue).
30 cout << MVC << endl; 5 - SPFA can deal with negative weight edge. If the graph has no negative cycle, SPFA runs well on
31 } it.
6 - If the graph has negative cycle(s), SPFA can also detect it as there must be some vertex (those
on the negative cycle)
7 that enters the queue for over V , 1 times.
8 **/
2.24 Restoring the path 9
10 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
11 ll INF = 0x3f3f3f3f3f3f3f3f;
12 ll mINF = 0xc0c0c0c0c0c0c0c0;
1 const int dr [] = {-1, 0, 1, 0}; 13
2 const int dc [] = {0, 1, 0, -1}; 14 int Head[N], Par[N], Next[M], To[M], Cost[M], Cnt[N], ne, n, m, u, v, st, tax;
3 const char dir [] = {’U’, ’R’, ’D’, ’L’}; 15 ll dis[N];
4 map <char, int> inv = { {’U’, 0}, {’R’, 1}, {’D’, 2}, {’L’, 3}}; 16 bool Inq[N];
5 17
6 /** Implicit Graphs 18 void addEdge(int from, int to, int cost) {
7 19 Next[++ne] = Head[from];
8 - in BFS, Dijkstra or Bellman-Ford function write -> Par[nr][nc] = dir[i ˆ 2] 20 Head[from] = ne;
9 - char Par[N][N] initialize with -1 21 Cost[ne] = cost;
10 - si start i 22 To[ne] = to;
11 - sj strat j 23 }
12 - fi target i 24
13 - fj target j 25 void _clear() {
14 - char dir and its map inv 26 memset(Head, 0, sizeof(Head[0]) * (n + 2));
15 - dr, dc 27 ne = 0;
16 **/ 28 }
17 29
18 string restorePath(int si, int sj, int fi, int fj) { 30 void _set() {
19 string s; 31 memset(dis, 0x3f, sizeof(dis[0]) * (n + 2));
20 if(Par[ei][ej] == -1) return s; 32 memset(Par, -1, sizeof(Par[0]) * (n + 2));
21 33 memset(Cnt, 0, sizeof(Cnt[0]) * (n + 2));
22 int ei = fi, ej = fj; 34 memset(Inq, 0, sizeof(Inq[0]) * (n + 2));
23 for(char i = Par[fi][fj]; (si ˆ fi) || (sj ˆ fj); i = Par[fi][fj]) { 35 }
24 s += dir[inv[i] ˆ 2]; 36
25 fi += dr[inv[i]]; 37 bool SPFA(int src) {
26 fj += dc[inv[i]]; 38 _set();
27 } 39
28 40 deque <int> Q;
29 reverse(s.begin(), s.end()); 41 Q.push_front(src);
30 return s; 42
31 } 43 dis[src] = 0;
32 44 Cnt[src] = 1;
33 /** Explicit Graphs (BFS, Dijkstra or Bellman-Ford) 45 Inq[src] = 1;
34 46
35 - int Par[N] initialize with -1 47 int node;
36 - ll dis[N] initialize with 0x3f 48 while(Q.size()) {
37 - ll INF = 0x3f3f3f3f3f3f3f3f 49 node = Q.front(); Q.pop_front(); Inq[node] = 0;
38 **/ 50
39 51 for(int i = Head[node]; i; i = Next[i])
40 vector <int> restorePath(int dest) { 52 if(dis[node] + Cost[i] < dis[To[i]]) {
41 vector <int> path; 53 dis[To[i]] = dis[node] + Cost[i];
42 if(dis[dest] == INF) return path; 54 Par[To[i]] = node;
43 55
44 for(int i = dest; ˜i; i = Par[i]) 56 if(!Inq[To[i]]) {
45 path.push_back(i); 57 if(++Cnt[To[i]] == n)
46 58 return true; // graph has a negative weight cycle
47 reverse(path.begin(), path.end()); 59
48 return path; 60 if(Q.size() && dis[To[i]] > dis[Q.front()])
49 } 61 Q.push_back(To[i]);
50 62 else
51 /** in case of Floyd-Warshall: 63 Q.push_front(To[i]);
52 64
53 - ll dis[N][N] initialize with 0x3f 65 Inq[To[i]] = true;
54 - ll INF = 0x3f3f3f3f3f3f3f3f 66 }
55 - int Par[N][N] initialize with Par[i][j] = i; 67 }
56 - in Floyd-Warshall function write -> Par[i][j] = Par[k][j]; 68 }
57 **/ 69 return false;
58 70 }
59 vector <int> restorePath(int st, int tr) {
60 vector <int> path;
61 if(dis[st][tr] == INF) return path;
62
63
64
for(int i = tr; st ˆ i; i = Par[st][i])
path.push_back(i);
2.26 Single source shortest path
65
66 path.push_back(st);
67 reverse(path.begin(), path.end()); 1 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
68 return path; 2 ll INF = 0x3f3f3f3f3f3f3f3f;
69 } 3
4 int Head[N], Par[N], Next[M], To[M], ne, n, m, u, v, st, tr;
5 ll dis[N];
6
7 void addEdge(int from, int to) {
2.25 Shortest path faster algorithml (spfa) 8
9
Next[++ne] = Head[from];
Head[from] = ne;
10 To[ne] = to;
11 }

10
1 /** Shortest Path Faster Algorithm : 12
2 - This algorithm runs in O(kE) where k is a number depending on the graph. 13 void _clear() {
 Al-Azhar University
14 memset(Head, 0, sizeof(Head[0]) * (n + 2)); 16 }
15 ne = 0; 17
16 } 18 void _clear() {
17 19 memset(Head, 0, sizeof(Head[0]) * (n + 2));
18 void BFS(int src) { 20 memset(dfs_num, 0, sizeof(dfs_num[0]) * (n + 2));
19 memset(dis, 0x3f, sizeof(dis[0]) * (n + 2)); 21 memset(compID, 0, sizeof(compID[0]) * (n + 2));
20 memset(Par, -1, sizeof(Par[0]) * (n + 2)); 22 memset(compSize, 0, sizeof(compSize[0]) * (n + 2));
21 23 ne = dfs_timer = top = ID = 0;
22 queue <int> Q; 24 }
23 Q.push(src); 25
24 dis[src] = 0; 26 void Tarjan(int node) {
25 27 dfs_num[node] = dfs_low[node] = ++dfs_timer;
26 int node; 28 in_stack[Stack[top++] = node] = true;
27 while(Q.size()) { 29
28 node = Q.front(); Q.pop(); 30 for(int i = Head[node]; i; i = Next[i]) {
29 for(int i = Head[node]; i; i = Next[i]) if(dis[To[i]] == INF) { 31 if(dfs_num[To[i]] == 0)
30 dis[To[i]] = dis[node] + 1; 32 Tarjan(To[i]);
31 Par[To[i]] = node; 33
32 Q.push(To[i]); 34 if(in_stack[To[i]])
33 } 35 dfs_low[node] = Min(dfs_low[node], dfs_low[To[i]]);
34 } 36 }
35 } 37
38 if(dfs_num[node] == dfs_low[node]) {
39 ++ID;
40 for(int cur = -1; cur ˆ node;) {
41 in_stack[cur = Stack[--top]] = false;
2.27 Single source shortest path (grid) 42
43
compID[cur] = ID;
++compSize[ID];
44 }
45 }
1 const int N = 1e3 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f; 46 }
2 ll INF = 0x3f3f3f3f3f3f3f3f; 47
3 48 void Tarjan() {
4 const int dr [] = {-1, 0, 1, 0}; 49 for(int i = 1; i <= n; ++i)
5 const int dc [] = {0, 1, 0, -1}; 50 if(dfs_num[i] == 0)
6 const char dir [] = {’U’, ’R’, ’D’, ’L’}; 51 Tarjan(i);
7 map <char, int> inv = { {’U’, 0}, {’R’, 1}, {’D’, 2}, {’L’, 3}}; 52 }
8
9 int dis[N][N], n, m;
10 char Par[N][N];
11
12
13
bool valid(int r, int c) {
return r >= 1 && r <= n && c >= 1 && c <= m && dis[r][c] == oo;
2.29 Topological sort (dfs)
14 }
15
16 void BFS(int sr, int sc) { 1 int Head[N], Next[M], To[M], ne, n, m, u, v;
17 memset(dis, 0x3f, sizeof(dis)); 2 bool vis[N];
18 memset(Par, -1, sizeof(Par)); 3 vector <int> t_sort;
19 4
20 queue < pair <int, int> > Q; 5 void addEdge(int from, int to) {
21 dis[sr][sc] = 0; 6 Next[++ne] = Head[from];
22 Q.push({sr, sc}); 7 Head[from] = ne;
23 8 To[ne] = to;
24 int r, c, nr, nc; 9 }
25 while(Q.size()) { 10
26 tie(r, c) = Q.front(); Q.pop(); 11 void DFS(int node) {
27 12 vis[node] = true;
28 for(int i = 0; i < 4; ++i) { 13 for(int i = Head[node]; i; i = Next[i])
29 nr = r + dr[i]; 14 if(!vis[To[i]])
30 nc = c + dc[i]; 15 DFS(To[i]);
31 16
32 if(!valid(nr, nc)) continue; 17 t_sort.push_back(node);
33 18 }
34 dis[nr][nc] = dis[r][c] + 1; 19
35 Par[nr][nc] = dir[i ˆ 2]; 20 vector <int> topological_sort(int n) {
36 Q.push({nr, nc}); 21
37 } 22 t_sort.clear();
38 } 23 for(int i = 1; i <= n; ++i) if(!vis[i])
39 } 24 DFS(i);
25
26 reverse(t_sort.begin(), t_sort.end());
27 return t_sort;
28 }
2.28 Tarjan (strongly connected components) 29
30 int main() {
31 cin >> n >> m;
32 while(m--) {
1 const int N = 1e5 + 9, M = 2e6 + 9, oo = 0x3f3f3f3f, Mod = 1e9 + 7; 33 cin >> u >> v;
2 ll INF = 0x3f3f3f3f3f3f3f3f; 34 addEdge(u, v);
3 35 }
4 int Head[N], To[M], Next[M], Cost[M]; 36
5 int dfs_num[N], dfs_low[N]; 37 vector <int> v = topological_sort(n);
6 int Stack[N], compID[N], compSize[N]; 38 for(int i : v)
7 int ne, n, m, u, v, w; 39 cout << i << ’ ’;
8 int dfs_timer, top, ID; 40 }
9 bool in_stack[N];
10
11 void addEdge(int from, int to, int cost = 0) {
12 Next[++ne] = Head[from];
13 Head[from] = ne; 2.30 Topological sort (kahns algorithm)

11
14 Cost[ne] = cost;
15 To[ne] = to;
 Al-Azhar University
1 int Head[N], Next[M], To[M], in[N], ne, n, m, u, v; 44 maxLength[node] = firstMax + secondMax + 2;
2 45 }
3 void addEdge(int from, int to) { 46
4 Next[++ne] = Head[from]; 47 void Solve()
5 Head[from] = ne; 48 {
6 To[ne] = to; 49 cin >> n;
7 } 50 _clear();
8 51
9 vector <int> kahn(int n) { 52 for(int i = 1; i < n; ++i) {
10 vector <int> ready, ret; 53 cin >> u >> v;
11 54 addEdge(u, v);
12 for(int i = 1; i <= n; ++i) 55 addEdge(v, u);
13 if(!in[i]) 56 }
14 ready.push_back(i); 57
15 58 dfs_toLeaf(1);
16 int node; 59 dfs_maxLength(1);
17 while(!ready.empty()) { 60
18 node = ready.back(); ready.pop_back(); 61 int diameter = 0;
19 ret.push_back(node); 62 for(int i = 1; i <= n; ++i)
20 63 if(maxLength[i] > diameter)
21 for(int i = Head[node]; i; i = Next[i]) 64 diameter = maxLength[i];
22 if(--in[To[i]] == 0) 65
23 ready.push_back(To[i]); 66 cout << diameter << endl;
24 } 67 }
25 return ret;
26 }
27
28 int main() {
29
30
cin >> n >> m;
while(m--) {
2.32 0-1 bfs
31 cin >> u >> v;
32 addEdge(u, v);
33 ++in[v]; 1 const int N = 1e5 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
34 } 2 ll INF = 0x3f3f3f3f3f3f3f3f;
35 3
36 vector <int> v = kahn(n); 4 int Head[N], Par[N], Next[M], To[M], Cost[M], ne, n, m, u, v, st, tr, tax;
37 if((int)v.size() == n) for(int i : v) 5 ll dis[N];
38 cout << i << ’ ’; 6
39 else 7 void addEdge(int from, int to, int cost) {
40 cout << "not a DAG!" << endl; 8 Next[++ne] = Head[from];
41 } 9 Head[from] = ne;
10 Cost[ne] = cost;
11 To[ne] = to;
12 }
13
2.31 Tree diameter 14
15
void _clear() {
memset(Head, 0, sizeof(Head[0]) * (n + 2));
16 ne = 0;
17 }
1 const int N = 3e5 + 9, M = 6e5 + 9, oo = 0x3f3f3f3f, Mod = 1e9 + 7; 18
2 ll INF = 0x3f3f3f3f3f3f3f3f; 19 void BFS(int src, int trg) {
3 20 memset(dis, 0x3f, sizeof(dis[0]) * (n + 2));
4 int Head[N], Next[M], To[M], Par[N], toLeaf[N], maxLength[N], ne, n, m, u, v, w; 21 memset(Par, -1, sizeof(Par[0]) * (n + 2));
5 22
6 void addEdge(int from, int to) { 23 deque <int> Q;
7 Next[++ne] = Head[from]; 24 Q.push_front(src);
8 Head[from] = ne; 25 dis[src] = 0;
9 To[ne] = to; 26
10 } 27 int node;
11 28 while(Q.size()) {
12 void _clear() { 29 node = Q.front(); Q.pop_front();
13 memset(Head, 0, sizeof(Head[0]) * (n + 2)); 30 if(node == trg) return;
14 memset(Par, -1, sizeof(Par[0]) * (n + 2)); 31
15 ne = 0; 32 for(int i = Head[node]; i; i = Next[i])
16 } 33 if(dis[node] + Cost[i] < dis[To[i]]) {
17 34 dis[To[i]] = dis[node] + Cost[i];
18 void dfs_toLeaf(int node, int par = -1) 35 if(Cost[i])
19 { 36 Q.push_back(To[i]);
20 toLeaf[node] = 0; 37 else
21 for(int i = Head[node]; i; i = Next[i]) 38 Q.push_front(To[i]);
22 if(To[i] != par) { 39 }
23 dfs_toLeaf(To[i], node); 40 }
24 if(toLeaf[To[i]] + 1 > toLeaf[node]) 41 }
25 toLeaf[node] = toLeaf[To[i]] + 1;
26 }
27 }
28
29
30
void dfs_maxLength(int node, int par = -1)
{
2.33 0-1 bfs (grid)
31 int firstMax = -1;
32 int secondMax = -1;
33 for(int i = Head[node]; i; i = Next[i]) 1 const int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
34 if(To[i] != par) { 2 const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
35 dfs_maxLength(To[i], node); 3 const char dir[] = {’D’, ’U’, ’R’, ’L’};
36 4
37 if(toLeaf[To[i]] > firstMax) { 5 const int N = 1e3 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f;
38 if(firstMax > secondMax) 6
39 secondMax = firstMax; 7 int dis[N][N], n, m, si, sj, ti, tj;
40 firstMax = toLeaf[To[i]]; 8 char grid[N][N];
41 } else if(toLeaf[To[i]] > secondMax) 9

12
42 secondMax = toLeaf[To[i]]; 10 bool valid(int r, int c) {
43 } 11 return r >= 1 && r <= n && c >= 1 && c <= m;
 Al-Azhar University
12 } 46 return find_set(u) == find_set(v);
13 47 }
14 int ZBFS(int sr, int sc, int tr, int tc) { 48
15 memset(dis, 0x3f, sizeof (dis)); // memset(dis, 0x3f, n * m) we don’t do that here 49 bool union_set(int u, int v) {
16 50 if(same_set(u, v)) return false;
17 deque <pair <int, int> > Q; 51
18 52 int x = find_set(u);
19 dis[sr][sc] = 0; 53 int y = find_set(v);
20 Q.push_front({sr, sc}); 54
21 55 if(siz[x] < siz[y]) swap(x, y);
22 int r, c, nr, nc, ncost; 56
23 while(Q.size()) { 57 par[y] = x;
24 tie(r, c) = Q.front(); Q.pop_front(); 58 siz[x] += siz[y];
25 if(r == tr && c == tc) return dis[r][c]; 59
26 60 --num_sets;
27 for(int i = 0; i < 8; ++i) { 61 return true;
28 nr = r + dr[i]; 62 }
29 nc = c + dc[i]; 63
30 64 int number_of_sets() {
31 if(!valid(nr, nc)) continue; 65 return num_sets;
32 ncost = (i != grid[r][c]); 66 }
33 67
34 if(dis[r][c] + ncost < dis[nr][nc]) { 68 int size_of_set(int u) {
35 dis[nr][nc] = dis[r][c] + ncost; 69 return siz[find_set(u)];
36 70 }
37 if(ncost) 71
38 Q.push_back({nr, nc}); 72 size_t size() {
39 else 73 return sz;
40 Q.push_front({nr, nc}); 74 }
41 } 75
42 } 76 void clear() {
43 } 77 par.clear();
44 return oo; 78 siz.clear();
45 } 79 sz = num_sets = 0;
80 }
81
82 void assign(size_t n) {
83 par.assign(n + 1, -1);

3 Data structures 84
85
86 }
siz.assign(n + 1, 1);
sz = num_sets = n;

87
88 map < int, vector <int> > groups(int st) {
3.1 Union find disjoint sets 89
90
map < int, vector <int> > ret;

91 for(size_t i = st; i < sz + st; ++i)

92 ret[find_set(i)].push_back(i);
1 /** 93
2 Maintain a set of elements partitioned into non-overlapping subsets. Each 94 return ret;
3 partition is assigned a unique representative known as the parent, or root. The 95 }
4 following implements two well-known optimizations known as union-by-size and 96 };
5 path compression. This version is simplified to only work on integer elements.
6
7 - find_set(u) returns the unique representative of the partition containing u.
8 - same_set(u, v) returns whether elements u and v belong to the same partition.
9
10
- union_set(u, v) replaces the partitions containing u and v with a single new
partition consisting of the union of elements in the original partitions.
3.2 Segment tree (rmq)
11
12 Time Complexity:
13 - O(a(n)) per call to find_set(), same_set(), and union_set(), where n is the 1 /** resources:
14 number of elements, and a(n) is the extremely slow growing inverse of the Ackermann function 2 1. https://codeforces.com/blog/entry/15729
15 (effectively a very small constant for all practical values of n). 3 2. https://codeforces.com/blog/entry/15890
16 4 3. https://codeforces.com/blog/entry/18051
17 Space Complexity: 5 4. https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/
18 - O(n) for storage of the disjoint set forest elements. practice-problems/algorithm/range-minimum-query/description/
19 - O(1) auxiliary for all operations. 6 **/
20 **/ 7
21 8 template <class T, class F = function <T(const T &, const T &)> >
22 class UnionFind { 9 class SegmentTree {
23 vector <int> par; 10 vector <T> _A;
24 vector <int> siz; 11 vector <T> ST;
25 int num_sets; 12 vector <T> LT;
26 size_t sz; 13 F func;
27 14 int _N;
28 public: 15
29 UnionFind() : par(1, -1), siz(1, 1), num_sets(0), sz(0) {} 16 public :
30 UnionFind(int n) : par(n + 1, -1), siz(n + 1, 1), num_sets(n), sz(n) {} 17 template <class iter>
31 18 SegmentTree(iter _begin, iter _end, const F _func = [](T a, T b) {return a <= b ? a : b;}) : func(
32 int find_set(int u) { _func) {
33 assert(u <= sz); 19 _N = distance(_begin, _end);
34 20 _N = (1 << (int)ceil(log2(_N)));
35 int leader; 21
36 for(leader = u; ˜par[leader]; leader = par[leader]); 22 _A.assign(_N + 1, 0);
37 23 ST.assign(_N << 1, 0);
38 for(int next = par[u]; u != leader; next = par[next]) { 24 LT.assign(_N << 1, 0);
39 par[u] = leader; 25
40 u = next; 26 __typeof(_begin) i = _begin;
41 } 27 for(int j = 1; i != _end; ++i, ++j)
42 return leader; 28 _A[j] = *i;
43 } 29

13
44 30 build(1, 1, _N);
45 bool same_set(int u, int v) { 31 }
 Al-Azhar University
32
33 void build(int p, int l, int r) {
34
35
if(l == r) {
ST[p] = _A[l];
3.3 Merge sort tree
36 return;
37 }
38 1 /** https://www.spoj.com/problems/KQUERY/
39 int mid = (l + r) >> 1; 2 **/
40 3
41 build(p + p, l, mid); 4 class SegmentTree {
42 build(p + p + 1, mid + 1, r); 5 vector <vector <int> > sTree;
43 6 vector <int> localArr;
44 const T & x = ST[p + p]; 7 int NP2, oo = 0x3f3f3f3f;
45 const T & y = ST[p + p + 1]; 8
46 9 public :
47 ST[p] = func(x, y); 10 template <class T>
48 } 11 SegmentTree(T _begin, T _end) {
49 12 NP2 = 1;
50 void update_range(int ul, int ur, int delta) { 13 int n = _end - _begin;
51 update_range(ul, ur, delta, 1, 1, _N); 14 while(NP2 < n) NP2 <<= 1;
52 } 15
53 16 sTree.assign(NP2 << 1, vector <int> ());
54 T query(int ql, int qr) { 17 localArr.assign(NP2 + 1, 0);
55 return query(ql, qr, 1, 1, _N); 18
56 } 19 __typeof(_begin) i = _begin;
57 20 for(int j = 1; i != _end; i++, ++j)
58 void update_point(int inx, int delta) { 21 localArr[j] = *i;
59 inx += _N - 1; 22
60 ST[inx] = delta; 23 build(1, 1, NP2);
61 24 }
62 while(inx > 1) { 25
63 inx >>= 1; 26 void build(int p, int l, int r) {
64 27 if(l == r) {
65 const T & x = ST[inx + inx]; 28 sTree[p].push_back(localArr[l]);
66 const T & y = ST[inx + inx + 1]; 29 return;
67 30 }
68 ST[inx] = func(x, y); 31
69 } 32 build(left(p), l, mid(l, r));
70 } 33 build(right(p), mid(l, r) + 1, r);
71 34
72 private : 35 merge(p);
73 void update_range(int ul, int ur, int delta, int p, int l, int r) { 36 }
74 if(r < ul || ur < l) 37
75 return; 38 int query(int ql, int qr, int k) {
76 39 return query(ql, qr, k, 1, 1, NP2);
77 if(ul <= l && r <= ur) { 40 }
78 ST[p] += delta; 41
79 LT[p] += delta; 42 private :
80 return; 43 int query(int ql, int qr, int k, int p, int l, int r) {
81 } 44 if(isOutside(ql, qr, l, r))
82 45 return 0;
83 propagate(p); 46
84 47 if(isInside(ql, qr, l, r)) {
85 int mid = (l + r) >> 1; 48 return sTree[p].end() - upper_bound(sTree[p].begin(), sTree[p].end(), k);
86 49 }
87 update_range(ul, ur, delta, p + p, l, mid); 50
88 update_range(ul, ur, delta, p + p + 1, mid + 1, r); 51 return query(ql, qr, k, left(p), l, mid(l, r)) + query(ql, qr, k, right(p), mid(l, r) + 1, r)
89 ;
90 const T & x = ST[p + p]; 52 }
91 const T & y = ST[p + p + 1]; 53
92 54 void merge(int p) {
93 ST[p] = func(x, y); 55 vector <int> & L = sTree[left(p)];
94 } 56 vector <int> & R = sTree[right(p)];
95 57
96 T query(int ql, int qr, int p, int l, int r) { 58 int l_size = L.size();
97 if(r < ql || qr < l) 59 int r_size = R.size();
98 return INT_MAX; 60 int p_size = l_size + r_size;
99 61
100 if(ql <= l && r <= qr) 62 L.push_back(INT_MAX);
101 return ST[p]; 63 R.push_back(INT_MAX);
102 64
103 propagate(p); 65 sTree[p].resize(p_size);
104 66
105 int mid = (l + r) >> 1; 67 for(int k = 0, i = 0, j = 0; k < p_size; ++k)
106 68 if(L[i] <= R[j])
107 const T & x = query(ql, qr, p + p, l, mid); 69 sTree[p][k] = L[i], i += (L[i] != INT_MAX);
108 const T & y = query(ql, qr, p + p + 1, mid + 1, r); 70 else
109 71 sTree[p][k] = R[j], j += (R[j] != INT_MAX);
110 return func(x, y); 72
111 } 73 L.pop_back();
112 74 R.pop_back();
113 void propagate(int p) { 75 }
114 if(LT[p]) { 76
115 ST[p + p] += LT[p]; 77 inline bool isInside(int ql, int qr, int sl, int sr) {
116 ST[p + p + 1] += LT[p]; 78 return (ql <= sl && sr <= qr);
117 LT[p + p] += LT[p]; 79 }
118 LT[p + p + 1] += LT[p]; 80
119 LT[p] = 0; 81 inline bool isOutside(int ql, int qr, int sl, int sr) {
120 } 82 return (sr < ql || qr < sl);
121 } 83 }

14
122 }; 84
85 inline int mid (int l, int r) {
 Al-Azhar University
86 return ((l + r) >> 1); 8 F func;
87 } 9
88 10 public :
89 inline int left(int p) { 11 SparseTable() = default;
90 return (p << 1); 12
91 } 13 template <class iter>
92 14 SparseTable(iter _begin, iter _end, F _func = [](T a, T b) { return a + b; }) : func(_func) {
93 inline int right(int p) { 15 _N = distance(_begin, _end);
94 return ((p << 1) | 1); 16
95 } 17 Log.assign(_N + 1, 0);
96 }; 18 for(int i = 2; i <= _N; ++i)
19 Log[i] = Log[i >> 1] + 1;
20
21 _LOG = Log[_N];
22
3.4 Sparse table (rmq) 23
24
_A.assign(_N + 1, 0);
ST.assign(_N + 1, vector <T> (_LOG + 1, 0));
25
26 __typeof(_begin) i = _begin;
1 template <class T, class F = function <T(const T&, const T&)> > 27 for(int j = 1; i != _end; ++i, ++j)
2 class SparseTable { 28 _A[j] = *i;
3 int _N; 29
4 int _LOG; 30 build();
5 vector <T> _A; 31 }
6 vector < vector <T> > ST; 32
7 vector <int> Log; 33 void build() {
8 F func; 34 for(int i = 1; i <= _N; ++i)
9 35 ST[i][0] = _A[i];
10 public : 36
11 SparseTable() = default; 37 for(int j = 1, k, d; j <= _LOG; ++j) {
12 38 k = (1 << j);
13 template <class iter> 39 d = (k >> 1);
14 SparseTable(iter _begin, iter _end, const F _func = less <T> ()) : func(_func) { 40
15 _N = distance(_begin, _end); 41 for(int i = 1; i + k - 1 <= _N; ++i) {
16 42 T const & x = ST[i][j - 1]; // starting subarray at index = i with length = 2ˆ{j - 1}
17 Log.assign(_N + 1, 0); 43 T const & y = ST[i + d][j - 1]; // starting subarray at index = i + d with length = 2ˆ{j - 1}
18 for(int i = 2; i <= _N; ++i) 44
19 Log[i] = Log[i >> 1] + 1; 45 ST[i][j] = func(x, y);
20 46 }
21 _LOG = Log[_N]; 47 }
22 48 }
23 _A.assign(_N + 1, 0); 49
24 ST.assign(_N + 1, vector <T> (_LOG + 1, 0)); 50 T query(int l, int r) {
25 51 int d = r - l + 1;
26 __typeof(_begin) i = _begin; 52 T ret = 0;
27 for(int j = 1; i != _end; ++i, ++j) 53
28 _A[j] = *i; 54 for(int i = l; d; i += lastBit(d), d -= lastBit(d))
29 55 ret = func(ret, ST[i][Log[lastBit(d)]]);
30 build(); 56
31 } 57 return ret;
32 58 }
33 void build() { 59
34 for(int i = 1; i <= _N; ++i) 60 int lastBit(int a) {
35 ST[i][0] = i; 61 return (a & -a);
36 62 }
37 for(int j = 1, k, d; j <= _LOG; ++j) { // the two nested loops below have overall time complexity 63 };
= O(n log n)
38 k = (1 << j);
39 d = (k >> 1);
40
41
42
for(int i = 1; i + k - 1 <= _N; ++i) {
T const & x = ST[i][j - 1]; // starting subarray at index = i with length = 2ˆ{j - 1}
3.6 Merge sort
43 T const & y = ST[i + d][j - 1]; // starting subarray at index = i + d with length = 2ˆ{j - 1}
44
45 ST[i][j] = func(_A[x], _A[y]) ? x : y; 1 /**
46 } 2 Time Complexity: Sorting arrays on different machines. Merge Sort is a recursive algorithm and time
47 } complexity can be expressed as following recurrence relation.
48 } 3
49 4 T(n) = 2T(n/2) + theta(n)
50 T query(int l, int r) { // this query is O(1) 5
51 int d = r - l + 1; 6 The above recurrence can be solved either using the Recurrence Tree method or the Master method. It
52 T const & x = ST[l][Log[d]]; falls in case II of Master Method and the solution of the recurrence is theta(nLogn). Time
53 T const & y = ST[l + d - (1 << Log[d])][Log[d]]; complexity of Merge Sort is theta(nLogn) in all 3 cases (worst, average and best) as merge
54 sort always divides the array into two halves and takes linear time to merge two halves.
55 return func(_A[x], _A[y]) ? x : y; 7 Auxiliary Space: O(n)
56 } 8 Algorithmic Paradigm: Divide and Conquer
57 }; 9 Sorting In Place: No in a typical implementation
10 Count Inversion of array: yes
11 https://discuss.codechef.com/t/iiti15-editorial/4427
12 Stable: Yes
13 **/
3.5 Sparse table (rsq) 14
15 ll inversions;
16
17 template <class T>
1 template <class T, class F = function <T(const T &, const T &)> > 18 void merge(T localArr [], int l, int mid, int r) {
2 class SparseTable { 19 int l_size = mid - l + 1;
3 int _N; 20 int r_size = r - mid;
4 int _LOG; 21
5 vector <T> _A; 22 T L[l_size + 1];

15
6 vector < vector <T> > ST; 23 T R[r_size + 1];
7 vector <int> Log; 24
 Al-Azhar University
25 for(int i = 0; i < l_size; ++i) L[i] = localArr[i + l]; 12
26 for(int i = 0; i < r_size; ++i) R[i] = localArr[i + mid + 1]; 13 __typeof(_begin) k = _begin;
27 14 for(int j = 0; k != _end; ++k, ++j)
28 T Mx; 15 localArray[j] = *k;
29 if(sizeof(T) == 4) Mx = INT_MAX; 16
30 else Mx = LONG_MAX; 17 round = min(round, sz);
31 18 for(int i = 0; i < round; ++i) /* n rounds -> n_th element **/
32 L[l_size] = R[r_size] = Mx; 19 for(int j = 0; j < sz - 1; ++j) if(localArray[j] > localArray[j + 1])
33 20 swap(localArray[j], localArray[j + 1]);
34 for(int k = l, i = 0, j = 0; k <= r; ++k) 21
35 if(L[i] <= R[j]) 22 k = _begin;
36 localArr[k] = L[i], i += (L[i] != Mx); 23 for(int j = 0; k != _end; ++k, ++j)
37 else 24 *k = localArray[j];
38 localArr[k] = R[j], j += (R[j] != Mx), inversions += l_size - i; 25 }
39 } 26
40 27 /**
41 template <class T> 28 After the first round of the algorithm, the largest element will be in the correct
42 void merge_sort(T localArr [], int l, int r) { 29 position, and in general, after k rounds, the k largest elements will be in the
43 if(r - l) 30 correct positions.
44 { 31 **/
45 int mid = (l + r) >> 1;
46 merge_sort(localArr, l, mid);
47 merge_sort(localArr, mid + 1, r);
48 merge(localArr, l, mid, r);
49 }
50
51
} 4 Mathematics
52 template <class T>
53 void merge_sort(T _begin, T _end) {
54 const int sz = _end - _begin;
55 __typeof(*_begin) localArray[sz]; 4.1 Euler totient function
56
57 __typeof(_begin) k = _begin;
58 for(int i = 0; k != _end; ++i, ++k)
59 localArray[i] = *k; 1 /**
60 2 Constraints:
61 merge_sort(localArray, 0, sz - 1); 3 1 <= n <= 1e7
62 4 2 <= a <= 10ˆ{14}
63 k = _begin; 5
64 for(int i = 0; k != _end; ++i, ++k) 6 Time Complexity:
65 *k = localArray[i]; 7 linear_sieve takes O(n)
66 } 8 Phi takes O(n / (ln(n) - 1.08))
9
10 Space Complexity:
11 O(MaxN + n / (ln(n) - 1.08))
12
3.7 Selection sort 13
14
Explanation:
Phi(n) = n * ((p1 - 1) / p1) * ((p2 - 1) / p2) *...* ((pk - 1) / pk)
15 Phi(n) = n * (1 - (1 / p1)) * (1 - (1 / p2)) *...* (1 - (1 / pk))
16
1 template <class T> 17 Applications:
2 void selection_sort(T _begin, T _end, int round) { 18 Eulers theorem:
3 const int sz = _end - _begin; 19 aˆphi(m) cong 1 (mod m) if a and m are relatively prime.
4 int localArray[sz]; 20
5 21 Fermats little theorem:
6 __typeof(_begin) k = _begin; 22 when m is a prime:
7 for(int i = 0; k != _end; ++i, ++k) 23 aˆ{m minus 1} cong 1 (mod m)
8 localArray[i] = *k; 24
9 25 As immediate consequence we also get the equivalence:
10 int MnInx; 26 aˆn cong aˆ{n mod phi(m)} (mod m)
11 round = min(sz, round); 27 This allows computing xˆn mod m for very big n, especially if n is the result of another
12 for(int i = 0; i < round; ++i) { computation,
13 MnInx = i; 28 as it allows to compute n under a modulo.
14 for(int j = i + 1; j < sz; ++j) 29 **/
15 if(localArray[j] < localArray[MnInx]) 30
16 MnInx = j; 31 int lp[N], Primes[664580], pnx; /** size of Primes = n / (ln(n) - 1.08) */
17 swap(localArray[MnInx], localArray[i]); 32
18 } 33 void linear_sieve(int n) {
19 34 for (int i = 2; i <= n; ++i) {
20 k = _begin; 35 if (lp[i] == 0) {
21 for(int i = 0; k != _end; ++i, ++k) 36 lp[i] = Primes[pnx++] = i;
22 *k = localArray[i]; 37 }
23 } 38 for (int j = 0, comp; j < pnx && Primes[j] <= lp[i] && (comp = i * Primes[j]) <= n; ++j) {
39 lp[comp] = Primes[j];
40 }
41 }
42 }
3.8 Bubble sort 43
44 ll Phi(ll a) { // for Queries
45 ll ret = a, p;
46 for (int i = 0; i < pnx && (p = Primes[i], true); ++i) {
1 /** 47 if (p * p > a) break;
2 Bubble sort consists of n rounds. On each round, the algorithm iterates 48 if (a % p) continue;
3 through the elements of the array. Whenever two consecutive elements are found 49 ret -= ret / p;
4 that are not in correct order, the algorithm swaps them. The algorithm can be 50 while (a % p == 0) a /= p;
5 implemented as follows: 51 }
6 52 if (a > 1) ret -= ret / a;
**/
7 53 return ret;
8 template <class T> 54 }
9 void bubble_sort(T _begin, T _end, int round) {

16
10 const int sz = _end - _begin;
11 int localArray[sz];
 Al-Azhar University
4.2 Euler phi (sieve) 10 O(MaxN + n / (ln(n) - 1.08)
11 */
12
13 int lp[N];
1 /* 14 int Primes[664580], pnx; /** size of Primes = n / (ln(n) - 1.08) */
2 Constraints: 15
3 1 <= n <= 1e7 16 void linear_sieve(int n) {
4 17 for (int i = 2; i <= n; ++i) {
5 Time Complexity: 18 if (lp[i] == 0) {
6 Phi_sieve takes O(n * ln(ln(n))) 19 lp[i] = Primes[pnx++] = i;
7 20 }
8 Space Complexity: 21 for (int j = 0, comp; j < pnx && Primes[j] <= lp[i] && (comp = i * Primes[j]) <= n; ++j) {
9 MaxN 22 lp[comp] = Primes[j];
10 */ 23 }
11 24 }
12 int EulerPhi[N]; 25 }
13 26
14 void Phi_sieve(int n) { 27 vector<pair<int, int>> Factorization(int n) {
15 for (int i = 1; i <= n; ++i) { 28 vector<pair<int, int>> ret;
16 EulerPhi[i] = i; 29 while (n > 1) {
17 } 30 int p = leastPrime[n], cnt = 0;
18 for (int i = 2; i <= n; ++i) { 31 while (n % p == 0) n /= p, ++cnt;
19 if (EulerPhi[i] == i) 32 ret.emplace_back(p, cnt);
20 for (int j = i; j <= n; j += i) { 33 }
21 EulerPhi[j] -= EulerPhi[j] / i; 34 return ret;
22 } 35 }
23 }
24 }

4.5 Miller rabin test

4.3 Extended wheel factorization
1 ll ModExp(ll base, ll e, ll mod) {
2 ll result;
1 /* 3 base %= mod;
2 Constraints: 4
3 1 <= n <= 1e7 5 for(result = 1; e; e >>= 1ll) {
4 2 <= a <= 1e{14} 6 if(e & 1ll)
5 7 result = ((i128)result * base) % mod;
6 Time Complexity: 8 base = ((i128)base * base) % mod;
7 linear_sieve takes O(n) 9 }
8 Factorization takes O(n / (ln(n) - 1.08)) 10 return result;
9 11 }
10 Space Complexity: 12
11 O(MaxN + n / (ln(n) - 1.08) 13 bool CheckComposite(ll n, ll p, ll d, int r) {
12 */ 14 ll a = ModExp(p, d, n);
13 15 if(a == 1 || a == n - 1)
14 int lp[N]; 16 return false;
15 int Primes[664580], pnx; /** size of Primes = n / (ln(n) - 1.08) */ 17
16 18 for(int i = 1; i < r; ++i) {
17 void linear_sieve(int n) { 19 a = ((i128)a * a) % n;
18 for (int i = 2; i <= n; ++i) { 20 if(a == n - 1)
19 if (lp[i] == 0) { 21 return false;
20 lp[i] = Primes[pnx++] = i; 22 }
21 } 23 return true;
22 for (int j = 0, comp; j < pnx && Primes[j] <= lp[i] && (comp = i * Primes[j]) <= n; ++j) { 24 }
23 lp[comp] = Primes[j]; 25
24 } 26 bool Miller(ll n) {
25 } 27 if(n < 2) return false;
26 } 28
27 29 int r; ll d;
28 vector<pair<ll, int>> Factorization(ll a) { 30 for(r = 0, d = n - 1; (d & 1ll) == 0; d >>= 1ll, ++r);
29 vector<pair<ll, int> > ret; 31
30 ll p; 32 for(int p : {2, 3, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
31 for (int i = 0, cnt; i < pnx && (p = Primes[i], true) && p * p <= a; ++i) { 33 if(n == p)
32 if (a % p) continue; 34 return true;
33 cnt = 0; 35 if(CheckComposite(n, p, d, r))
34 while (a % p == 0) a /= p, ++cnt; 36 return false;
35 ret.emplace_back(p, cnt); 37 }
36 } 38 return true;
37 if (a > 1) ret.emplace_back(a, 1); 39 }
38 return ret;
39 }

4.6 Mobius function

4.4 Least prime factorization
1 /**
2 Constraints:
1 /* 3 1 <= x <= 1e7
2 Constraints: 4 2 <= n <= 10ˆ{14}
3 1 <= n <= 1e7 5
4 6 Time Complexity:
5 Time Complexity: 7 linear_sieve takes O(x)
6 linear_sieve takes O(n) 8 mobius takes O(n / (ln(n) - 1.08))
7 Factorization takes O(log(n)) 9

17
8 10 Space Complexity:
9 Space Complexity: 11 O(MaxN + n / (ln(n) - 1.08))
 Al-Azhar University
12 */ 21
13 22 for (int j = 0, comp; j < pnx && Primes[j] <= lp[i] && (comp = i * Primes[j]) <= x; ++j) {
14 int lp[N], Primes[664580], pnx; /** size of Primes = n / (ln(n) - 1.08) */ 23 lp[comp] = Primes[j];
15 24 }
16 void linear_sieve(int x) { 25 }
17 for (int i = 2; i <= x; ++i) { 26 }
18 if (lp[i] == 0) { 27
19 lp[i] = Primes[pnx++] = i; 28 ll phi_factorial(int n) {
20 } 29 ll ret = 1;
21 30 for (int i = 2; i <= n; ++i) {
22 for (int j = 0, comp; j < pnx && Primes[j] <= lp[i] && (comp = i * Primes[j]) <= x; ++j) { 31 ret = ret * (lp[i] == i ? i - 1 : i);
23 lp[comp] = Primes[j]; 32 }
24 } 33 return ret;
25 } 34 }
26 }
27
28 int mobius(ll n) {
29 ll p, pp;
30
31
char mob = 1;
for (int i = 0; i < pnx && (p = Primes[i], pp = p * p, true); ++i) {
4.9 Pisano periodic sequence
32 if (pp > n) break;
33 if (n % p) continue;
34 if (n % pp == 0) return 0; 1 /** Algorithm 1: **/
35 n /= p; 2
36 mob = -mob; 3 /** Constraints :
37 } 4 1 <= n <= CR
38 if (n > 1) mob = -mob; 5 Where CR stands for your computing resources. In my case,
39 return mob; 6 CR = 100,000,000
40 } 7 ----------------
8 The algorithm is constructed around the ideas that a Pisano sequence always starts with 0 and 1,
and that this sequence of Fibonacci
9 numbers taken modulo n can be constructed for each number by adding the previous remainders and
taking into account the modulo n.
4.7 Mobius (sieve) 10
11
----------------

12 definition:
13 The sequence of Fibonacci numbers {F_n} is periodic modulo any modulus m (Wall 1960), and the
1 /* period (mod m)
2 Constraints: 14 is the known as the Pisano period pi(m) (Wrench 1969). For m=1, 2, ..., the values of pi(m) are
3 1 <= n <= 1e7 15 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, ... (OEIS A001175).
4 16
5 Time Complexity: 17 Since pi(10)=60, the last digit of F_n repeats with period 60, as first noted by Lagrange in 1774
6 mu_sieve takes O(n) (Livio 2002, p. 105).
7 18 The last two digits repeat with a period of 300, and the last three with a period of 1500.
8 Space Complexity: 19 In 1963, Geller found that the last four digits have a period of 15000 and the last five a period
9 O(MaxN) of 150000.
10 */ 20 Jarden subsequently showed that for d>=3, the last d digits have a period of 15*10ˆ(d minus 1) (
11 Livio 2002, pp. 105-106).
12 int mu[N], lp[N], Primes[78522], pnx; 21 The sequence of Pisano periods for n=1, 10, 100, 1000, ... are therefore 60, 300, 1500, 15000,
13 150000, 1500000, ... (OEIS A096363).
14 void mu_sieve(int n) { 22 pi(m) is even if m>2 (Wall 1960). pi(m)=m iff m=24*5ˆ(k-1) for some integer k>1 (Fulton and Morris
15 mu[1] = 1; 1969, Wrench 1969).
16 fill(mu, mu + N, 1); 23
17 for (int i = 2; i <= n; ++i) { 24 resources :
18 if (lp[i] == 0) { 25 1. https://webbox.lafayette.edu/˜reiterc/nt/qr_fib_ec_preprint.pdf
19 lp[i] = Primes[pnx++] = i; 26 2. https://www.youtube.com/watch?v=Nu-lW-Ifyec&ab_channel=Numberphile
20 mu[i] = -1; 27 4. http://webspace.ship.edu/msrenault/fibonacci/fib.htm
21 } 28 5. https://www.theoremoftheday.org/Binomial/PeriodicFib/TotDPeriodic.pdf
22 for (int j = 0, nxt; j < pnx && Primes[j] <= lp[i] && (nxt = i * Primes[j]) <= n; ++j) { 29 7. http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibmaths.html#fibmod
23 lp[nxt] = Primes[j]; 30 8. http://webspace.ship.edu/msrenault/fibonacci/FibThesis.pdf
24 mu[nxt] = (lp[i] == Primes[j] ? 0 : -mu[i]); 31 9. https://www.fq.math.ca/Scanned/1-2/vinson.pdf
25 } 32 **/
26 } 33
27 } 34 vector <int> pisano_periodic_sequence(int n) {
35 vector <int> period;
36
37 int current = 0, next = 1;
38 period.push_back(current);
4.8 Phi factorial 39
40 if(n < 2) return period;
41 current = (next += current) - current;
42
1 /** 43 while(current != 0 || next != 1) {
2 Constraints: 44 period.push_back(current);
3 1 <= x <= 1e7 45 current = current + next >= n ? (next += current - n) + (n - current) : (next += current) -
4 2 <= n <= 1e7 current;
5 46 }
6 Time Complexity: 47 return period;
7 linear_sieve takes O(x) 48 }
8 phi_factorial takes O(n) 49
9 50 /** ************************************************************************************** **/
10 Space Complexity: 51 /** Algorithm 2: **/
11 O(MaxN + n / (ln(n) - 1.08)) 52
12 */ 53 /** constraints:
13 54 1 <= n <= 10ˆ{18}
14 int lp[N], Primes[664580], pnx; /** number of primes = n / (ln(n) - 1.08) **/ 55 --------------
15 56 problem statement (https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page
16 void linear_sieve(int x) { =show_problem&problem=4479):
17 for (int i = 2; i <= x; ++i) { 57 For any integer n, the sequence of Fibonacci numbers F_i taken mod n is periodic.
18 if (lp[i] == 0) { 58 define K(n) = the length of the period of the Fibonacci sequence reduced mod n.

18
19 lp[i] = Primes[pnx++] = i; 59 The task is to print the length of the period of this sequence K(n).
20 } 60 --------------
 Al-Azhar University
61 Definition: 148 }
62 The Pisano period pi(n) is a multiplicative function, that is if a and b are coprime than pi( 149
ab) = pi(a) * pi(b). 150 ll n;
63 So we need only concern ourselves with the value of pi(pˆk) for prime p. 151 vector <int> primes;
64 (Factoring even a large number is still better than brute force periodicity search.) 152 matrix <ll> fibMatrix = {{1, 1},
65 153 {1, 0}
66 It is hypothesized that p(pˆk) = pˆ{k - 1} * pi(p) and since no counterexamples are known to exist, 154 };
67 you might as well use that in your algorithm. 155
68 156 i128 gcd(i128 a, i128 b) {
69 So, how to calculate pi(p) efficiently? There are two special cases and two general cases 157 while (a && b)
70 158 a > b ? a %= b : b %= a;
71 pi(2ˆk) = 3*2ˆ{k - 1} 159 return a + b;
72 pi(5ˆk) = 4*5ˆk 160 }
73 161
74 If p cong 1 or p cong 9 (mod10) then pi(p) | p - 1 162 i128 lcm(i128 a, i128 b) {
75 If p cong 3 or p cong 7 (mod10) then pi(p) | 2 * (p + 1) , and by an odd divisor too. 163 return a / gcd(a, b) * b;
76 164 }
77 The last two statements give us a relatively small number of cases to try (after factoring p - 1 165
or 2*(p + 1) .) 166 vector < array <ll, 2> > factorize(ll x) {
78 Now use your favorite formula to calculate large values of the Fibonacci numbers F(x) (mod p). 167 vector < array <ll, 2> > ret;
79 [See Michal answer to What is a fast algorithm to find the remainder of the division of a huge 168 for(int i = 0; 1ll * primes[i] * primes[i] <= x; ++i) {
Fibonacci number by some big integer?](https://www.quora.com/Whats-a-fast-algorithm-to-find- 169 if(x % primes[i]) continue;
the-remainder-of-the-division-of-a-huge-Fibonacci-number-by-some-big-integer/answer/Michal- 170
Fori%C5%A1ek) . 171 int cnt = 0;
80 To test a candidate period R , calculate F(R) (mod p) and F(R + 1) (mod p). 172 while (x % primes[i] == 0) {
81 If these are equal to F(0) = 0 and F(1) = 1 , then pi(p) | R. 173 cnt++;
82 174 x /= primes[i];
83 It might be that p - 1 or 2*(p + 1) have a lot of divisors, but we dont need to try them all. 175 }
84 Suppose qˆk | R for some prime q. 176 ret.push_back({primes[i], cnt});
85 Then test R/q . If that doesnt produce a cycle, then pi(p) must have factor qˆk , 177 }
86 and we can leave it in and go on to other factors. 178
87 Otherwise, we can use R/q as our new starting point and repeat the process. 179 if(x > 1) ret.push_back({x, 1});
88 Thus we have to do a number of checks proportional to Omega(2*(p + 1)) , not d(2*(p + 1)). 180 return ret;
89 181 }
90 ------------ 182
91 Donald Wall proved several other properties, some of which you may find interesting: 183 matrix <ll> MatMul(matrix <ll> A, matrix <ll> B, ll mod) {
92 If m > 2, k(m) is even. 184 int ra = A.size(), cb = B[0].size(), ca = A[0].size();
93 For any even integer n > 2, there exists m such that k(m) = n. 185 matrix <i128> C(ra, vector <i128> (cb));
94 k(m) <= (mˆ2) - 1 186
95 k(2ˆn) = 3 * 2ˆ{n - 1} 187 for(int i = 0; i < ra; ++i)
96 k(5ˆn) = 4 * 5ˆn 188 for (int j = 0; j < cb; ++j) {
97 If n > 2, k(10ˆn) = 15 * 10ˆ{n - 1} 189 C[i][j] = 0;
98 k(2 * 5ˆn) = 6n 190 for(int k = 0; k < ca; ++k)
99 **/ 191 C[i][j] = (C[i][j] + (i128)A[i][k] * B[k][j]);
100 192 }
101 #pragma GCC optimize ("Ofast") 193
102 194 matrix <ll> ret(ra, vector <ll> (cb));
103 #include <bits/stdc++.h> 195 for(int i = 0; i < ra; ++i)
104 196 for (int j = 0; j < cb; ++j)
105 #define endl ’\n’ 197 ret[i][j] = C[i][j] % mod;
106 198
107 using namespace std; 199 return ret;
108 200 }
109 typedef long long ll; 201
110 typedef __int128 i128; 202 matrix <ll> MatPow(matrix <ll> A, ll p, ll mod) {
111 typedef __int128_t ui128; 203 int r = A.size(), c = A[0].size();
112 204 assert(r == c && p);
113 template <class T> 205 matrix <ll> result = A;
114 using matrix = vector < vector <T> >; 206 p--;
115 207
116 template <class T> string to_string(T x) { 208 while(p) {
117 int sn = 1; 209 if(p & 1ll) result = MatMul(result, A, mod);
118 if(x < 0) sn = -1, x *= sn; 210 A = MatMul(A, A, mod);
119 string s = ""; 211 p >>= 1ll;
120 do { 212 }
121 s = "0123456789"[x % 10] + s, x /= 10; 213 return result;
122 } while(x); 214 }
123 return (sn == -1 ? "-" : "") + s; 215
124 } 216 i128 ModExp(i128 a, ll p) {
125 217 i128 result = 1;
126 auto str_to_int(string x) { 218 while(p) {
127 ui128 ret = (x[0] == ’-’ ? 0 : x[0] - ’0’); 219 if(p & 1ll) result = result * a;
128 for(int i = 1; i < (int)x.size(); ++i) ret = ret * 10 + (x[i] - ’0’); 220 a *= a;
129 return (x[0] == ’-’ ? -1 * (i128)ret : ret); 221 p >>= 1ll;
130 } 222 }
131 223 return result;
132 istream & operator >> (istream & in, i128 & i) noexcept { 224 }
133 string s; 225
134 in >> s; 226 ll nthFib(ll n, ll mod) {
135 i = str_to_int(s); 227 return MatPow(fibMatrix, n, mod)[0][1];
136 return in; 228 }
137 } 229
138 230 bool is_period(ll n, ll mod) {
139 ostream & operator << (ostream & os, const i128 i) noexcept { 231 return nthFib(n, mod) == 0 && nthFib(n + 1, mod) == 1;
140 os << to_string(i); 232 }
141 return os; 233
142 } 234 ll solver(ll x, ll mod) {
143 235 vector < array <ll, 2> > factors = factorize(x);
144 void Fast() { 236 for(int i = 0; i < (int)factors.size(); ++i) {
145 cin.sync_with_stdio(0); 237 while(x % factors[i][0] == 0 && is_period(x / factors[i][0], mod))

19
146 cin.tie(0); 238 x /= factors[i][0];
147 cout.tie(0); 239 }
 Al-Azhar University
240 return x; 26
241 } 27 int c = 0;
242 28 for (int i = 7; i <= x; i += inc[c++]) {
243 ll pisano_prime(ll val) { 29 if (isPrime[i]) {
244 if(val == 2) return 3; 30 Primes[pnx++] = i;
245 if(val == 5) return 20; 31 int d = inx[i % 30];
246 if(val % 10 == 1 || val % 10 == 9) 32 for (ll j = i * 1ll * i; j <= x; j += i * inc[d++]) {
247 return solver(val - 1, val); 33 isPrime[j] = false;
248 34 if (d == 8) d = 0;
249 return solver(2 * (val + 1), val); 35 }
250 } 36 }
251 37 if (c == 8) c = 0;
252 const int N = 1e7 + 9; 38 }
253 bitset <N> isPrime; 39 }
254
255 void Precomputation_Sieve() {
256 isPrime.set();
257 int _sqrt = sqrtl(N);
258
259 for(int i = 5; i <= _sqrt; i += 6) {
4.11 wheel sieve
260 if(isPrime[i]) for (int j = i * i; j < N; j += i + i) isPrime.reset(j);
261 i += 2;
262 if(isPrime[i]) for (int j = i * i; j < N; j += i + i) isPrime.reset(j); 1 /**
263 i -= 2; 2 Constraints:
264 } 3 1 <= n <= 1e9
265 } 4 2 <= x <= 9700000
266 5
267 vector <int> Primes(int n) { 6 Time Complexity:
268 vector <int> _Primes; 7 wheel_sieve takes O(n / ln(ln(n)))
269 8 coPrimes takes O(x * ln(ln(x)))
270 if(n >= 2) _Primes.push_back(2); 9
271 if(n >= 3) _Primes.push_back(3); 10 Space Complexity:
272 11 O(MaxN / 32 + n / (ln(n) - 1.08) + x)
273 for (int i = 5; i <= n; i += 6) { 12 **/
274 if(isPrime[i]) _Primes.push_back(i); 13
275 i += 2; 14 bitset<N> isPrime;
276 if(isPrime[i]) _Primes.push_back(i); 15 int inx[30100];
277 i -= 2; 16 int Primes[50908031], pnx; /** size of Primes = n / (ln(n) - 1.08) */
278 } 17
279 return _Primes; 18 vector<int> coPrimes(int x) {
280 } 19 int basis[5] = {3, 5, 7, 11, 13};
281 20
282 void initialize() 21 vector<int> ret;
283 { 22 bitset<30100> isCoprime;
284 Precomputation_Sieve(); 23 isCoprime.set();
285 primes = Primes(N); 24
286 } 25 for (int b : basis)
287 26 for (int d = b * b; d <= x; d += b << 1)
288 void Solve() { 27 isCoprime.reset(d);
289 initialize(); 28
290 cin >> n; 29 for (int i = 17; i <= x; i += 2)
291 vector < array <ll, 2> > factors = factorize(n); 30 if (isCoprime[i]) ret.push_back(i);
292 31
293 i128 ans = 1; 32 ret.push_back(x + 1);
294 for (int i = 0; i < (int)factors.size(); ++i) { 33 ret.push_back(x + 17);
295 ans = lcm(ans, (i128)pisano_prime(factors[i][0]) * ModExp(factors[i][0], factors[i][1] - 1)); 34 return ret;
296 } 35 }
297 cout << ans << endl; 36
298 } 37 void wheel_sieve(int n) {
38 int basis[6] = {2, 3, 5, 7, 11, 13};
39 vector<int> wheel = coPrimes(2 * 3 * 5 * 7 * 11 * 13);
40 int sz = wheel.size();
41
4.10 Simple sieve 42
43
for (int k = 0; k < sz; ++k)
inx[wheel[k]] = k;
44
45 isPrime.set();
1 /** 46 inx[1] = sz - 2;
2 constraints: 47 int inc[sz - 1];
3 1 <= n <= 1e8 48
4 49 for (int i = 1; i < sz; ++i)
5 Time complexity: 50 inc[i - 1] = wheel[i] - wheel[i - 1];
6 O(n * ln(ln(sqrt(n))) + n) 51
7 52 for (int p : basis) {
8 Space Complexity: 53 if (n >= p)
9 O(MaxN + n / (ln(n) - 1.08)) 54 Primes[pnx++] = p;
10 **/ 55 }
11 56
12 bool isPrime[N]; 57 int c = 0;
13 int Primes[664580], pnx; /** size of Primes = n / (ln(n) - 1.08) */ 58 for (ll i = 17; i <= n; i += inc[c++]) {
14 59 if (isPrime[i]) {
15 void sieve(int x) { 60 Primes[pnx++] = i;
16 int basis[3] = {2, 3, 5}; 61 int d = inx[i % 30030];
17 int wheel[8] = {7, 11, 13, 17, 19, 23, 29, 1}; 62 for (ll j = i * i; j <= n; j += i * inc[d++]) {
18 int inc[8] = {4, 2, 4, 2, 4, 6, 2, 6}; 63 isPrime.reset(j);
19 int inx[31]; 64 if (d == sz - 1) d = 0;
20 65 }
21 memset(inx, 0, sizeof(inx)); 66 }
22 memset(isPrime, true, sizeof(isPrime)); 67 if (c == sz - 1) c = 0;
23 68 }
69 }

20
24 for (int p : basis) if (x > p) Primes[pnx++] = p;
25 for (int i = 0; i < 8; ++i) inx[wheel[i]] = i;
 Al-Azhar University
1 const int N = 1e3+ 9, M = 1e3 + 9, oo = 0x3f3f3f3f;
2 queue <int> Q;
4.12 Linear sieve 3
4 int husband[N], wife[N], Next[N], order[N][N], pref[N][N], n, v;
5
6 void _clear() {
1 /** 7 memset(wife, 0, sizeof(wife[0]) * (n + 2));
2 Constraints: 8 memset(husband, 0, sizeof(husband[0]) * (n + 2));
3 1 <= n <= 1e7 9 memset(Next, 0, sizeof(Next[0]) * (n + 2));
4 10 }
5 Time Complexity: 11
6 linear_sieve takes O(n) 12 void engage(int man, int woman) {
7 13 int exWife = wife[man];
8 Space Complexity: 14 wife[man] = woman;
9 O(MaxN + n / (ln(n) - 1.08)) 15 husband[woman] = man;
10 **/ 16
11 17 if(exWife)
12 int lp[N]; 18 Q.push(exWife);
13 int Primes[664580], pnx; /** size of Primes = n / (ln(n) - 1.08) */ 19 }
14 20
15 void linear_sieve(int n) { 21 void Solve() {
16 for (int i = 2; i <= n; ++i) { 22 _clear();
17 if (lp[i] == 0) { 23 cin >> n;
18 lp[i] = Primes[pnx++] = i; 24
19 } 25 for(int i = 1; i <= n; ++i)
20 for (int j = 0, comp; j < pnx && Primes[j] <= lp[i] && (comp = i * Primes[j]) <= n; ++j) { 26 for(int j = 1; j <= n; ++j)
21 lp[comp] = Primes[j]; 27 cin >> pref[i][j];
22 } 28
23 } 29 for(int i = 1; i <= n; ++i)
24 } 30 for(int j = 1; j <= n; ++j) {
31 cin >> v;
32 order[i][v] = j;
33 }
34
35 for(int i = 1; i <= n; ++i)
4.13 Segmented sieve 36 Q.push(i);
37
38 int man, woman;
39 while(Q.size()) {
1 /** 40 woman = Q.front(); Q.pop();
2 constraints: 41 man = pref[woman][++Next[woman]];
3 1 <= l, r <= 1e{14} 42
4 1 <= r - l + 1 <= 1e7 43 if(!wife[man] || order[man][woman] < order[man][wife[man]])
5 2 <= x <= 1e7 44 engage(man, woman);
6 45 else
7 Time complexity: 46 Q.push(woman);
8 segmented_sieve takes O((r - l + 1) * ln(ln(r))) 47 }
9 linear_sieve takes O(n) 48
10 49 for(int i = 1; i <= n; ++i)
11 Space Complexity: 50 cout << husband[i] << endl;
12 O(2 * MaxN + n / (ln(n) - 1.08)) 51 }
13 **/
14
15 int lp[N];
16 int Primes[664580], pnx; /** size of Primes = n / (ln(n) - 1.08) */
17 bool isPrime[N];
18
19 void linear_sieve(int n) {
5 String processing
20 for (int i = 2; i <= n; ++i) {
21 if (lp[i] == 0) {
22
23 }
lp[i] = Primes[pnx++] = i;
5.1 Trie
24 for (int j = 0, comp; j < pnx && Primes[j] <= lp[i] && (comp = i * Primes[j]) <= n; ++j) {
25 lp[comp] = Primes[j];
26 } 1 class Trie {
27 } 2 private:
28 } 3 Trie* children[26]; // Pointer = 8 Byte; 8*26 = 208 Byte
29
4 int prefixs, words; // 8 Byte
30 vector<ll> segmented_sieve(ll l, ll r) { 5 bool iseow; // 1 Byte
31 l += l == 1; 6 char cur_letter; // 1 Byte
32 int limit = r - l + 1; 7 vector <string> lex;
33 vector<ll> ret; 8 priority_queue <pair <int, string>, vector <pair <int, string>>, greater <pair <int, string>>>
34 memset(isPrime, true, sizeof(isPrime)); occurrence; // small at top
35
9
36 ll p; 10 public:
37 for (int i = 0; i < pnx && (p = Primes[i], true); ++i) { 11 Trie(char lett = ’\0’) {
38 for (ll j = max(p * p, (l + p - 1) / p * p); j <= r; j += p) 12 memset(children, 0, sizeof(children));
39 isPrime[j - l] = false; 13 prefixs = words = 0;
40 } 14 iseow = false;
41
15 cur_letter = lett;
42 for (int i = 0; i < limit; ++i) 16 }
43 if (isPrime[i]) 17
44 ret.emplace_back(i + l); 18 void insert(string &str) { // O(l)
45 return ret; 19 Trie* cur = this;
46 } 20 int inx, strsz = str.size();
21 for(int i = 0; i < strsz; ++i) {
22 inx = str[i] - ’a’;
23 if(cur->children[inx] == nullptr)
24 cur->children[inx] = new Trie(str[i]);
4.14 The stable marriage problem 25

21
26 cur = cur->children[inx];
27 cur->prefixs++;
 Al-Azhar University
28 } 119 if(!search_prefix(pref))
29 cur->iseow = true; 120 return;
30 cur->words++; 121
31 } 122 Trie* cur = this;
32 123 int inx, presz = pref.size();
33 int search_word(string &str) { // O(l) 124 for(int i = 0; i < presz; ++i) {
34 Trie* cur = this; 125 inx = pref[i] - ’a’;
35 int inx, strsz = str.size(); 126 cur = cur->children[inx];
36 for(int i = 0; i < strsz; ++i) { 127 }
37 inx = str[i] - ’a’; 128
38 if(cur->children[inx] == nullptr) { 129 for(int i = 0; i < 26; ++i) if(cur->children[i] != nullptr) {
39 return 0; 130 dfs2(cur->children[i], string(1, cur->children[i]->cur_letter));
40 } 131 }
41 cur = cur->children[inx]; 132
42 } 133 vector <string> st;
43 return cur->words; 134 while(!occurrence.empty()) {
44 } 135 st.emplace_back(pref + occurrence.top().second);
45 136 occurrence.pop();
46 int search_prefix(string &str) { // O(l) 137 }
47 Trie* cur = this; 138 if(cur->iseow) {
48 int inx = 0, strsz = str.size(); 139 st.emplace_back(pref);
49 for(int i = 0; i < strsz; ++i) { 140 }
50 inx = str[i] - ’a’; 141 while(!st.empty()) {
51 if(cur->children[inx] == nullptr) { 142 cout << st.back() << endl;
52 return 0; 143 st.pop_back();
53 } 144 }
54 cur = cur->children[inx]; 145 }
55 } 146 };
56 return cur->prefixs;
57 }
58
59 bool erase(string &str) {
60
61
if(!search_word(str))
return false;
5.2 Knuth Morris Pratt (kmp)
62
63 Trie* cur = this;
64 int inx, strsz = str.size(); 1 /**
65 for(int i = 0; i < strsz; ++i) { 2 * KMP(Knuth-Morris-Pratt) Algorithm
66 inx = str[i] - ’a’; 3 ** Longest Prefix
67 if(--cur->children[inx]->prefixs == 0) { 4 *** proper prefix = all prefixes except the whole string
68 cur->children[inx] = nullptr; 5 *** propre suffix = all suffixes except the whole string
69 return true; 6 ** Prefix Function = Failure Function
70 } 7 *** Given String P of len m, Find F[m];
71 cur = cur->children[inx]; 8 *** let t = P[0....i]
72 } 9 *** f[i] = length of the longest proper prefix of t that is suffix of t
73 if(--cur->words == 0) { 10 *** calculating i different ways
74 cur->iseow = false; 11 *** match the pattern against itself
75 } 12 *** O(m) for failure function
76 return true; 13 *** O(n) for KMP
77 } 14 **/
78 15
79 private: 16 vector <int> LongestPrefix(string &p) {
80 void dfs(Trie* node, string s) { // lex order dfs -> traverse all the strings starting from root 17 int psz = p.size();
81 if(node->iseow) { 18 vector <int> longest_prefix(psz, 0);
82 lex.emplace_back(s); 19
83 } 20 for(int i = 1, k = 0; i < psz; ++i) {
84 21 while(k && p[k] != p[i]) k = longest_prefix[k - 1];
85 for(int j = 0; j < 26; ++j) 22 longest_prefix[i] = (p[k] == p[i] ? ++k : k);
86 if(node->children[j] != nullptr) { 23 }
87 dfs(node->children[j], s + string(1, node->children[j]->cur_letter)); 24 return longest_prefix;
88 } 25 }
89 } 26
90 27 vector <int> KMP(string &s, string &p) {
91 void dfs2(Trie* node, string s) { // autocomplete dfs -> traverse all the strings starting from the 28 int ssz = s.size(), psz = p.size();
end of the given prefix 29
92 if(node->iseow) { 30 vector <int> longest_prefix = LongestPrefix(p), matches;
93 if(occurrence.size() < 10) { 31
94 occurrence.push(make_pair(node->words, s)); 32 for(int i = 0, k = 0; i < ssz; ++i) {
95 } else { 33 while(k && p[k] != s[i]) k = longest_prefix[k - 1]; // Fail go back
96 if(node->words > occurrence.top().first) { 34 k += (p[k] == s[i]);
97 occurrence.pop(); 35
98 occurrence.push(make_pair(node->words, s)); 36 if(k == psz) {
99 } 37 matches.emplace_back(i - psz + 1);
100 } 38 k = longest_prefix[k - 1]; // faill safe and find another pattern
101 } 39 }
102 40 }
103 for(int i = 0; i < 26; ++i) if(node->children[i] != nullptr) { 41 return matches;
104 dfs2(node->children[i], s + string(1, node->children[i]->cur_letter)); 42 }
105 }
106 }
107
108 public:
109
110
111
vector <string> lex_order() { // all strings in lexicographical order
lex.clear();
Trie* cur = this;
6 Geometry
112 for(int i = 0; i < 26; ++i) if(cur->children[i] != nullptr) {
113 dfs(cur->children[i], string(1, cur->children[i]->cur_letter));
114
115
}
return lex;
6.1 Point
116 }

22
117
118 void autocomplete(string &pref) { // suggest top ten words with max frequency 1 /**
 Al-Azhar University
2 notes: 22 ret.push_back({sr, sc});
3 EPS = 1e-9 23 reverse(ret.begin(), ret.end());
4 ------------------------------------ 24 return ret;
5 Integers | Doubles | 25 }
6 ------------------------------------ 26
7 a == b | fabs(a - b) < EPS | 27 bool valid(int r, int c) {
8 a <= b | a < b + EPS | 28 return r >= 0 && r < n && c >= 0 && c < m && grid[r][c] != ’%’;
9 a >= b | a + EPS > b | 29 }
10 a < b | a + EPS < b | 30
11 a > b | a > b + EPS | 31 /** admissible heuristic **/
12 x >= 0.0 | x > -EPS | 32 int manhattanDistance(int x1, int y1, int x2, int y2) {
13 x <= 0.0 | x < EPS | 33 return (abs(x1 - x2) + abs(y1 - y2));
14 ----------------------------------- 34 }
15 **/ 35
16 36 int Astar(int sr, int sc, int tr, int tc) {
17 class point { 37 memset(dis, 0x3f, sizeof (dis));
18 public : 38 memset(Par, -1, sizeof (Par));
19 ld x, y; 39
20 40 priority_queue <tuple <int, int, int> > Q;
21 point() = default; 41
22 point(ld _x, ld _y) : x(_x), y(_y) {} 42 dis[sr][sc] = 0;
23 43 Q.push({-manhattanDistance(sr, sc, tr, tc), sr, sc});
24 bool operator < (point other) const { 44
25 if(fabs(x - other.x) > EPS) // if(x != other.x) 45 int hcost, r, c, nr, nc;
26 return x < other.x; 46 while(Q.size()) {
27 return y < other.y; 47 tie(hcost, r, c) = Q.top(); Q.pop();
28 } 48 if(r == tr && c == tc) return dis[r][c];
29 49
30 bool operator == (point other) const { 50 for(int i = 0; i < 4; ++i) {
31 return ((fabs(x - other.x) < EPS) && (fabs(y - other.y) < EPS)); // " < EPS " equal to " == zero " 51 nr = r + dr[i];
32 } 52 nc = c + dc[i];
33 53
34 bool operator > (point other) const { 54 if(!valid(nr, nc)) continue;
35 if(fabs(x - other.x) > EPS) 55
36 return x > other.x; 56 if(dis[r][c] + 1 < dis[nr][nc]) {
37 return y > other.y; 57 dis[nr][nc] = dis[r][c] + 1;
38 } 58 Par[nr][nc] = dir[i ˆ 2];
39 59 Q.push({-dis[nr][nc] -manhattanDistance(nr, nc, tr, tc), nr, nc});
40 ld dist(point other) { // Euclidean distance 60 }
41 ld dx = this->x - other.x; 61 }
42 ld dy = this->y - other.y; 62 }
43 return sqrtl(dx * dx + dy * dy); 63 return -1;
44 } 64 }
45 65
46 ld DEG_to_RAD(ld theta) { 66 void Solve() {
47 return theta * PI / 180.0; 67 cin >> si >> sj >> ti >> tj >> n >> m;
48 } 68 for(int i = 0; i < n; ++i)
49 69 for(int j = 0; j < m; ++j)
50 ld RAD_to_DEG(ld theta) { 70 cin >> grid[i][j];
51 return theta * 180.0 / PI; 71
52 } 72 cout << Astar(si, sj, ti, tj) << endl;
53 73 vector < pair <int, int> > path = restorePath(si, sj, ti, tj);
54 point rotate(ld theta) { 74
55 ld rad = DEG_to_RAD(theta); 75 for(auto point : path)
56 return point(cos(theta) * x - sin(theta) * y, 76 cout << point.first << " " << point.second << endl;
57 sin(theta) * x + cos(theta) * y); 77 }
58 }
59 };

7.2 Mo’s algorithm

7 More advanced topics 1 const int N = 3e4 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f, Mod = 1e9 + 7;
2 const ll INF = 0x3f3f3f3f3f3f3f3f;
3 const int BLK = 256;
7.1 A* algorithm 4
5 struct query {
6 int l, r, id, blk;
7
1 const int dr [] = {-1, 0, 1, 0}; 8 query() = default;
2 const int dc [] = {0, 1, 0, -1}; 9 query(int _l, int _r, int _id) {
3 const char dir [] = {’U’, ’R’, ’D’, ’L’}; 10 l = _l;
4 map <char, int> inv = { {’U’, 0}, {’R’, 1}, {’D’, 2}, {’L’, 3}}; 11 r = _r;
5 12 id = _id;
6 const int N = 1e3 + 9, M = 2e5 + 9, oo = 0x3f3f3f3f; 13 blk = l / BLK;
7 const ll INF = 0x3f3f3f3f3f3f3f3f; 14 }
8 15
9 char grid[N][N], Par[N][N]; 16 bool operator < (const query other) const {
10 int dis[N][N], n, m, si, sj, ti, tj; 17 if(blk ˆ other.blk)
11 18 return blk < other.blk;
12 vector < pair <int, int> > restorePath(int sr, int sc, int tr, int tc) { 19 return (blk & 1) ? r < other.r : r > other.r;
13 vector < pair <int, int> > ret; 20 }
14 if(dis[tr][tc] == oo) return ret; 21 } queries[M];
15 22
16 for(char i = Par[tr][tc]; (sr ˆ tr) || (sc ˆ tc); i = Par[tr][tc]) { 23 int res[M], freq[M << 3], cur;
17 ret.push_back({tr, tc}); 24
18 tr += dr[inv[i]]; 25 void add(int id) {
19 tc += dc[inv[i]]; 26 cur += (++freq[id] == 1);

23
20 } 27 }
21 28
 Al-Azhar University
29 void remove(int id) { 43 cin >> n;
30 cur -= (--freq[id] == 0); 44 for(int i = 1; i <= n; ++i) cin >> a[i];
31 } 45
32 46 build();
33 int get_res() { 47 cin >> q;
34 return cur; 48 while(q--) {
35 } 49 cin >> type >> x >> y;
36 50 if(type == 0) {
37 int cur_l, cur_r, l, r, n, q, a[N]; 51 cin >> z;
38 52 cout << query(x, y, z) << endl;
39 void Solve() { 53 }
40 cin >> n; 54 else
41 for(int i = 1; i <= n; ++i) cin >> a[i]; 55 update(x, y);
42 56 }
43 cin >> q; 57 }
44 for(int i = 1; i <= q; ++i) {
45 cin >> l >> r;
46 queries[i] = query(l, r, i);
47 }
48
49
50
sort(queries + 1, queries + 1 + q);
8 Miscellaneous
51 cur_l = 1, cur_r = 0; // assign to right invalid index
52 for(int i = 1; i <= q; ++i) {
53 int ql = queries[i].l;
54
55
int qr = queries[i].r; 8.1 C++ template
56 // Add right
57 while(cur_r < qr) add(a[++cur_r]);
58 // Add left
1 #pragma GCC optimize("Ofast")
59 while(cur_l > ql) add(a[--cur_l]);
2
60 // Remove right
3 #include <bits/stdc++.h>
61 while(cur_r > qr) remove(a[cur_r--]);
4
62 // Remove left
5 #define endl ’\n’
63 while(cur_l < ql) remove(a[cur_l++]);
6 #define read(a, n) for(int i = 0; i < n; cin >> a[i++]);
64
7
65 res[queries[i].id] = get_res();
8 #define debug(args ...) { \
66 }
9 string _s = #args; \
67
10 replace(_s.begin(), _s.end(), ’,’, ’ ’); \
68 for(int i = 1; i <= q; ++i)
11 stringstream _ss(_s); \
69 cout << res[i] << "\n";
12 istream_iterator<string> _it(_ss); \
70 }
13 err(_it, args); \
14 }
15
16 using namespace std;
17
7.3 Square root decomposition 18 using i128 = __int128_t;
19 using i64 = int64_t;
20 using i32 = int32_t;
21
1 const int N = 5e5 + 9, M = 1e3 + 9, oo = 0x3f3f3f3f, Mod = 1e9 + 7;
22 using u128 = __uint128_t;
2 const ll INF = 0x3f3f3f3f3f3f3f3f;
23 using u64 = uint64_t;
3 const int BLK = 256;
24 using u32 = uint32_t;
4
25 using ld = long double;
5 int n, q, a[N], type, x, y, z;
26
6 vector <int> bs[M];
27 const int N = 2e5 + 9, M = 3e7 + 9, oo = 0x3f3f3f3f, Mod = 1e9 + 7;
7
28 const ld eps = 1e-9;
8 int query(int l, int r, int val) {
29
9 int cur_l = l / BLK;
30 void err(istream_iterator<string> it) {}
10 int cur_r = r / BLK;
31 template<typename T, typename ... Args>
11 int ans = 0;
32 void err(istream_iterator<string> it, T a, Args ... args) {
12
33 cerr << *it << " = " << a << endl;
13 if(cur_l == cur_r) {
34 err(++it, args ...);
14 for (int i = l; i <= r; ++i)
35 }
15 ans += (a[i] >= val);
36
16 } else {
37 void fast() {
17 for(int i = l, _end = (cur_l + 1) * BLK; i < _end; ++i)
38 ios_base::sync_with_stdio(false);
18 ans += (a[i] >= val);
39 cin.tie(nullptr);
19 for(int i = cur_l + 1; i <= cur_r - 1; ++i)
40 }
20 ans += bs[i].end() - lower_bound(bs[i].begin(), bs[i].end(), val);
41
21 for(int i = cur_r * BLK; i <= r; ++i)
42 void file() {
22 ans += (a[i] >= val);
43 freopen("input.in", "r", stdin);
23 }
44 freopen("output.out", "w", stdout);
24 return ans;
45 }
25 }
46
26
47 void Solve() {
27 void build() {
48
28 for(int i = 0; i < n; ++i)
49 }
29 bs[i / BLK].emplace_back(a[i]);
50
30
51 int main() {
31 for(int i = 0; i < M; ++i)
52 fast();
32 sort(bs[i].begin(), bs[i].end());
53 // file();
33 }
54
34
55 int t = 1; // cin >> t;
35 void update(int id, int delta) {
56 for(int i = 1; i <= t; ++i) {
36 int pos = lower_bound(bs[id / BLK].begin(), bs[id / BLK].end(), a[id]) - bs[id / BLK].begin();
57 Solve();
37 bs[id / BLK][pos] = delta;
58 }
38 sort(bs[id / BLK].begin(), bs[id / BLK].end());
59 }
39 a[id] = delta;
40 }

24
41
42 void Solve() {
 Al-Azhar University
8.2 Double comparison
8.4 Gcd & Lcm
1 bool approximatelyEqual(double a, double b, double epsilon) {
2 return fabs(a - b) <= ((fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
3 }
1 i64 gcd(i64 a, i64 b) { // binary GCD uses about 60% fewer bit operations
4
2 if (!a) return b;
5 bool essentiallyEqual(double a, double b, double epsilon) {
3
6 return fabs(a - b) <= ((fabs(a) > fabs(b) ? fabs(b) : fabs(a)) * epsilon);
4 u64 shift = __builtin_ctzll(a | b);
7 }
5 a >>= __builtin_ctzll(a);
8
6
9 bool definitelyGreaterThan(double a, double b, double epsilon) {
7 while (b) {
10 return (a - b) > ((fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
8 b >>= __builtin_ctzll(b);
11 }
9
12
10 if (a > b)
13 bool definitelyLessThan(double a, double b, double epsilon) {
11 swap(a, b);
14 return (b - a) > ((fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * epsilon);
12 b -= a;
15 }
13 }
14 return a << shift;
15 }
16
8.3 Fast input/output 17
18
i64 lcm(i64 a, i64 b) {
return a / gcd(a, b) * b;
19 }

1 /**
2 Fast Input/Output method for C++:
3 1. cin(with sync_with_stdio(false) & cin.tie(nullptr)):
4
5
- int:
- |n = 5e6| => 420ms
8.5 Modular calculations
6 - |n = 1e7| => 742ms
7 - ll:
8 - |n = 5e6| => 895ms 1 /*
9 2 - It also has important applications in many tasks unrelated to arithmetic, since it can be used
10 2. read (using getchar()): with any operations that have the property of associativity:
11 - int: 3 */
12 - |n = 5e6| => 173ms 4
13 - |n = 1e7| => 172ms 5 // 1. Modular Exponentiation
14 - ll: 6
15 - |n = 5e6| => 340ms 7 i64 binExp(i64 a, i64 b, i64 p) {
16 **/ 8 i64 res;
17 9 for (res = 1; b; b >>= 1) {
18 ll readll () { 10 if (b & 1ll)
19 bool minus = false; 11 res = res * a % p;
20 unsigned long long result = 0; 12 a = a * a % p;
21 char ch; 13 }
22 ch = getchar(); 14 return res;
23 15 }
24 while (true) { 16
25 if (ch == ’-’) break; 17 // 2. Modular Multiplication
26 if (ch >= ’0’ && ch <= ’9’) break; 18
27 ch = getchar(); 19 i64 binMul(i64 a, i64 b, i64 p) {
28 } 20 i64 res;
29 21 a %= p;
30 if (ch == ’-’) minus = true; 22 for (res = 0; b; b >>= 1) {
31 else result = ch - ’0’; 23 if (b & 1ll)
32 24 res = (res + a) % p;
33 while (true) { 25 a = (a + a) % p;
34 ch = getchar(); 26 }
35 if (ch < ’0’ || ch > ’9’) break; 27 return res;
36 result = result * 10 + (ch - ’0’); 28 }
37 } 29
38 30 // 3. Modular Multiplicative Inverse
39 if (minus) return -(ll)result; 31
40 return result; 32 i64 modInv(i64 b, i64 p) {
41 } 33 return binExp(b, p - 2, p); // Guaranteed that p is a Prime Number
42 34 }
43 int readi () {
44 bool minus = false;
45 unsigned int result = 0;
46 char ch;
47
48
ch = getchar(); 8.6 Debugging tools
49 while (true) {
50 if (ch == ’-’) break;
51 if (ch >= ’0’ && ch <= ’9’) break; 1 #define rforeach(_it, c) for(__typeof((c).rbegin()) _it = (c).rbegin(); _it != (c).rend(); ++_it)
52 ch = getchar(); 2 #define foreach(_it, c) for(__typeof((c).begin()) _it = (c).begin(); _it != (c).end(); ++_it)
53 } 3 #define all(a) (a).begin(), (a).end()
54 4 #define sz(a) (int)a.size()
55 if (ch == ’-’) minus = true; 5 #define endl ’\n’
56 else result = ch - ’0’; 6
57 7 typedef int64_t ll;
58 while (true) { 8
59 ch = getchar(); 9 #if __cplusplus >= 201402L
60 if (ch < ’0’ || ch > ’9’) break; 10
61 result = result * 10 + (ch - ’0’); 11 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
62 } 12 template <class T> T rnd_in_rng(T a, T b)
63 13 { return uniform_int_distribution <ll> (a, b)(rng); /** [a, b] **/}
64 if (minus) return -(int)result; 14

25
65 return result; 15 template <typename F, typename S>
66 } 16 ostream & operator << (ostream & os, const pair <F, S> & p)
 Al-Azhar University
17 { return os << "(" << p.first << ", " << p.second << ")"; } 13
18 14 template <typename K, typename V, typename Comp = less <K>>
19 template <typename F, typename S> 15 using indexed_map = tree <K, V, Comp, rb_tree_tag, tree_order_statistics_node_update>;
20 ostream & operator << (ostream & os, const map <F, S> & _mp)
21 { os << "["; foreach(it, _mp) { if(it != _mp.begin()) os << ", "; os << it->first << " = " << it->
second; } return os << "]"; }
22
23
24
template <typename T>
ostream & operator << (ostream & os, const vector <T> & _v)
8.9 Pseudo random number generator
25 { os << "["; foreach(it, _v) { if(it != _v.begin()) os << ", "; os << *it; } return os << "]"; }
26
27 template <typename T> 1 /** pseudo-random number generator | C++xx >= C++11 **/
28 ostream & operator << (ostream & os, const set <T> & _st) 2
29 { os << "["; foreach(it, _st) { if(it != _st.begin() ) os << ", "; os << *it; } return os << "]"; } 3 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
30 4
31 template <typename T, size_t S> 5 T myRand(T a, T b) {
32 ostream & operator << (ostream & os, const array <T, S> & _ar) 6 return uniform_int_distribution <T> (a, b)(rng);
33 { os << "["; foreach(it, _ar) { if(it != _ar.begin() ) os << ", "; os << *it; } return os << "]"; } 7 }
34
35 template <typename T> void write(T _begin, T _end)
36 { for(auto i = _begin; i != _end; ++i) cout << (*i) << ’ ’; cout << endl; }
37
38
39
template <typename T> void read(T _begin, T _end)
{ for(auto i = _begin; i != _end; ++i) cin >> (*i); }
8.10 Stress test
40
41 #endif
42 1 #include <bits/stdc++.h>
43 clock_t start_time; 2
44 string run_time() 3 using namespace std;
45 { return to_string((clock() - (double)start_time) / CLOCKS_PER_SEC) + " sec"; } 4
46 5 #define endl ’\n’
47 #ifndef ONLINE_JUDGE 6
48 #include <sys/resource.h> 7 using i128 = __int128_t;
49 void resize_stack() 8 using i64 = int64_t;
50 { 9 using i32 = int32_t;
51 rlimit rlim; 10 using i16 = int16_t;
52 getrlimit(RLIMIT_STACK, &rlim); 11 using i8 = int8_t;
53 rlim.rlim_cur = (1 << 28); 12
54 setrlimit(RLIMIT_STACK, &rlim); 13 using u128 = __uint128_t;
55 } 14 using u64 = uint64_t;
56 #else 15 using u32 = uint32_t;
57 void resize_stack() {}; 16 using u16 = uint16_t;
58 #endif 17 using u8 = uint8_t;
18
19 void fast() {
20 ios_base::sync_with_stdio(false);
21 cin.tie(nullptr);
8.7 Overloaded operators to accept 128 bit integer 22
23
}

24 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
25
1 typedef __uint128_t ui128; 26 /** 64-bit signed int Generator
2 typedef __int128 i128; 27 **/
3 28 i64 int64(i64 a, i64 b) {
4 template <class T> string to_string(T x) { 29 return uniform_int_distribution <i64> (a, b)(rng);
5 int sn = 1; if(x < 0) sn = -1, x *= sn; string s = ""; 30 }
6 do { s = "0123456789"[x % 10] + s, x /= 10; } while(x); 31
7 return (sn == -1 ? "-" : "") + s; 32 /** Customize your Generator depending on the input
8 } 33 **/
9 34 void gen () {
10 auto str_to_int(string x) { 35 ofstream cout("input.in");
11 ui128 ret = (x[0] == ’-’ ? 0 : x[0] - ’0’); 36 i32 t = 2;
12 for(int i = 1; i < x.size(); ++i) ret = ret * 10 + (x[i] - ’0’); 37 cout << t << endl;
13 return (x[0] == ’-’ ? -1 * (i128)ret : ret); 38
14 } 39 while (t--) {
15 40 i32 n = int64(1, 100), m = int64(1, 100);
16 istream & operator >> (istream & in, i128 & i) noexcept { string s; in >> s; i = str_to_int(s); return 41 cout << n << " " << m << endl;
in; } 42
17 ostream & operator << (ostream & os, const i128 i) noexcept { os << to_string(i); return os; } 43 while (m--) {
18 istream & operator >> (istream & in, ui128 & i) noexcept { string s; in >> s; i = str_to_int(s); 44 i32 u = int64(1, n), v = int64(1, n), c = int64(1, 4);
return in; } 45 cout << u << " " << v << " " << c << endl;
19 ostream & operator << (ostream & os, const ui128 i) noexcept { os << to_string(i); return os; } 46 }
47 }
48 }
49
50 i32 main (i32 arg, char* args[]) {
8.8 Policy based data structures 51
52
fast();

53 i32 tc = 0;
54 i32 limit = 100;
1 #if __cplusplus >= 201402L 55 if(arg != 3) return 0;
2 #include <ext/pb_ds/assoc_container.hpp> 56
3 #include <ext/pb_ds/tree_policy.hpp> 57 string flags = "g++ -Wall -Wextra -Wshadow -Og -g -Ofast -std=c++17 -D_GLIBCXX_ASSERTIONS -DDEBUG -
4 #endif ggdb3 -fsanitize=address,undefined -fmax-errors=2 -o ";
5 58 string ex = ".cpp", bf, oz, pr;
6 #if __cplusplus >= 201402L 59
7 using namespace __gnu_cxx; 60 bf = flags + args[1] + " " + args[1] + ex;
8 using namespace __gnu_pbds; 61 oz = flags + args[2] + " " + args[2] + ex;
9 #endif 62 char bff[bf.size() + 1];
10 63 char ozz[oz.size() + 1];

26
11 template <class T, typename Comp = less <T> > 64 strcpy(bff, bf.c_str());
12 using indexed_set = tree <T, null_type, Comp, rb_tree_tag, tree_order_statistics_node_update>; 65 strcpy(ozz, oz.c_str());
 Al-Azhar University
66 85 ifstream brute_forces("brute_force.out");
67 // compile command 86 ifstream optimizes("optimized.out");
68 system(bff); 87
69 system(ozz); 88 string brute_force, optimized;
70 89 getline(brute_forces, brute_force, (char)EOF);
71 ex = ".out"; 90 getline(optimizes, optimized, (char)EOF);
72 pr = "./"; 91
73 bf = pr + args[1] + " < input.in > " + args[1] + ex; 92 if(brute_force != optimized) {
74 oz = pr + args[2] + " < input.in > " + args[2] + ex; 93 cerr << "Wrong Answer" << endl;
75 strcpy(bff, bf.c_str()); 94 break;
76 strcpy(ozz, oz.c_str()); 95 } else if (tc == limit) {
77 96 cout << "Accepted insha’a Allah" << endl;
78 while (++tc <= limit) { 97 }
79 gen(); 98 }
80 cerr << tc << endl; 99 }
81 // run command
82 system(bff);
83 system(ozz);
84

27