Template

基本

头文件

  • 普通青年
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cctype>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
  • 文艺青年
1
#include <bits/stdc++.h>
  • 二逼青年
1
2
//#include <cstdio>
#include <windows.h>

$I/O$ 优化

  • 一般读入优化
1
2
3
4
5
6
int read() {
int u = 0; bool f = false; char c = getchar();
for (;!isdigit(c); c = getchar()) if (c == '-') f = true;
for (; isdigit(c); c = getchar()) u = (u << 1) + (u << 3) + c - '0';
return f ? -u : u;
}
  • $fread$
1
2
3
4
5
6
7
8
9
10
struct io {
char op[1 << 26], *s;
io() { fread(s = op, 1, 1 << 26, stdin); }
int read(bool f = false, int u = 0) {
while (*s < 48) if (*s++ == '-') f = true;
while (*s > 47) u = (u << 1) + (u << 3) + *s++ - '0';
return f ? -u : u;
}
}ip;
#define read ip.read
  • 一般输出优化
1
2
3
4
5
6
7
char op[20]; int tp;
void write(int u) {
bool f = u < 0; u = f ? -u : u; tp = 0;
for (; u; u /= 10) op[++tp] = u % 10 + '0';
if (f) putchar('-'); if(!tp) putchar('0');
for (;tp; --tp) putchar(op[tp]);
}

离散化

1
2
3
4
5
6
7
8
9
const int maxn = 1e5 + 10; int aux[maxn];
void discretization(int *begin, int *end) {
aux[0] = 0;
for (int *i = begin; i != end; ++i) aux[++aux[0]] = *i;
std::sort(aux + 1, aux + 1 + aux[0]);
aux[0] = std::unique(aux + 1, aux + 1 + aux[0]) - aux - 1;
for (int *i = begin; i != end; ++i)
*i = std::lower_bound(aux + 1, aux + 1 + aux[0], *i) - aux;
}

数据结构

并查集

1
2
3
4
5
6
7
const int maxn = 1e5 + 10;
struct mergefindSet {
int fa[maxn];
void clear(int n) { for (int i = 0; i <= n; i++) fa[i] = i; }
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) { fa[find(x)] = find(y); }
};

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
const int maxn = 1e5 + 10;
struct BIT {
int s[maxn], maxs;
void clear(int n) {
for (int i = 0; i <= n; i++) s[i] = 0; maxs = n;
}
void add(int p, int v) {
for (int i = p; i <= maxs; i += i & -i) s[i] += v;
}
int sum(int p, int v = 0) {
for (int i = p; i; i -= i & -i) v += s[i]; return v;
}
}

线段树

  • 普通线段树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int maxn = 1e5 + 10;
namespace Seg {
ll sum[maxn << 2], tag[maxn << 2];
void pushup(int p) {
sum[p] = sum[p << 1] + sum[p << 1 | 1];
}
void build(int p, int l, int r) {
if (l == r) return (void)(scanf("%lld", &sum[p]));
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
pushup(p);
}
void pushdown(int p, int l, int r) {
if (!tag[p]) return;
int mid = l + r >> 1;
sum[p << 1] += (mid - l + 1) * tag[p];
sum[p << 1 | 1] += (r - mid) * tag[p];
tag[p << 1] += tag[p]; tag[p << 1 | 1] += tag[p];
tag[p] = 0;
}
void add(int p, int l, int r, int lp ,int rp, ll v) {
if (l == lp && r == rp) {
sum[p] += (r - l + 1) * v;
tag[p] += v; return;
}pushdown(p, l, r); int mid = l + r >> 1;
if(rp <= mid) add(p << 1, l, mid, lp, rp, v);
else if(lp > mid) add(p << 1 | 1, mid + 1, r, lp, rp, v);
else add(p << 1, l, mid, lp, mid, v), add(p << 1 | 1, mid + 1, r, mid + 1, rp, v);
pushup(p);
}
ll query(int p, int l, int r, int lp, int rp) {
if (l == lp && r == rp) return sum[p];
pushdown(p, l, r); int mid = l + r >> 1;
if(rp <= mid) return query(p << 1, l, mid, lp, rp);
else if(lp > mid) return query(p << 1 | 1, mid + 1, r, lp, rp);
else return query(p << 1, l, mid, lp, mid) + query(p << 1 | 1, mid + 1, r, mid + 1, rp);
}
}
  • 标记永久化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int maxn = 1e5 + 10;
namespace Seg {
#define ls (p << 1)
#define rs (p << 1 | 1)
ll sum[maxn << 2], all[maxn << 2];
void build(int p, int l, int r) {
if (l == r) return void(sum[p] = read());
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
sum[p] = sum[ls] + sum[rs];
}
void update(int p, int l, int r, int lq, int rq, int val) {
if (l == lq && r == rq)
return void(all[p] += val);
sum[p] += (ll) val * (rq - lq + 1);
int mid = l + r >> 1;
if (rq <= mid) update(ls, l, mid, lq, rq, val);
else if (lq > mid) update(rs, mid + 1, r, lq, rq, val);
else update(ls, l, mid, lq, mid, val), update(rs, mid + 1, r, mid + 1, rq, val);
}
ll query(int p, int l, int r, int lq, int rq) {
ll ans = all[p] * (rq - lq + 1);
if (l == lq && r == rq)
return ans + sum[p];
int mid = l + r >> 1;
if (rq <= mid) return query(ls, l, mid, lq, rq) + ans;
else if (lq > mid) return query(rs, mid + 1, r, lq, rq) + ans;
else return query(ls, l, mid, lq, mid) + query(rs, mid + 1, r, mid + 1, rq) + ans;
}
}

平衡树

  • $fhq~Treap$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
namespace Treap {
#define nl NULL
struct node {
node *son[2];
int _rand, _size, _value;
node(int val) {
son[0] = son[1] = nl;
_rand = rand(); _size = 1;
_value = val;
}
int size() {
return this == nl ? 0 : _size;
}
void maintain() {
_size = son[0]->size() + 1 + son[1]->size();
}
}*root, *a, *b, *c, *d;
node *merge(node *x, node *y) {
if (!x || !y) return x ? x : y;
if (x->_rand < y->_rand) {
x->son[1] = merge(x->son[1], y);
x->maintain(); return x;
}
else {
y->son[0] = merge(x, y->son[0]);
y->maintain(); return y;
}
}
node *merge(node *x, node *y, node *z) {
return merge(merge(x, y), z);
}
void split(node *t, int val, node* &x, node* &y) {
if (!t) return void(x = y = nl);
if (val > t->_value)
x = t, split(t->son[1], val, x->son[1], y);
else
y = t, split(t->son[0], val, x, y->son[0]);
t->maintain();
}
void insert(int val) {
split(root, val, a, b);
root = merge(a, new node(val), b);
}
void erase(int val) {
split(root, val, a, b);
split(b, val + 1, b, c);
d = b;
if (b) b = merge(b->son[0], b->son[1]);
root = merge(a, b, c);
delete d;
}
int kth(int rank) {
for (node *t = root; t;) {
if (rank == t->son[0]->size() + 1) return t->_value;
if (rank <= t->son[0]->size()) t = t->son[0];
else rank -= t->son[0]->size() + 1, t = t->son[1];
}
}
int find(int val) {
split(root, val, a, b);
int r = a->size() + 1;
root = merge(a, b);
return r;
}
int pre(int val) {
int r = 0;
for (node *t = root; t;) {
if (val > t->_value) {
r = t->_value;
t = t->son[1];
}else t = t->son[0];
}return r;
}
int nxt(int val) {
int r = 0;
for (node *t = root; t;) {
if (val < t->_value) {
r = t->_value;
t = t->son[0];
}else t = t->son[1];
}return r;
}
void print() {
printf("#");
for (int i = 1; i <= root->size(); i++)
printf(" %d #", kth(i));
printf("\n");
}
}
  • 可持久化$Treap$(指针版$MLE$)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
namespace Treap {
#define nl NULL
struct node {
node *son[2];
int _value, _size, _rand;
node(int val = 0) {
_value = val; _size = 1; _rand = rand();
son[0] = son[1] = nl;
}
int size() {
return this == nl ? 0 : _size;
}
void maintain() {
if (this == nl) return;
_size = son[0]->size() + 1 + son[1]->size();
}
void print() {
if (this == nl) return;
son[0]->print();
printf("%d # ", _value);
son[1]->print();
}
}*a, *b, *c, *d;
std::vector<node*>root(1);
node *copynode(node *t) {
node *p = new node; *p = *t; return p;
}
void split(node *t, int val, node* &x, node* &y) {
if (!t) return void(x = y = nl);
if (t->_value < val)
x = copynode(t), split(t->son[1], val, x->son[1], y);
else
y = copynode(t), split(t->son[0], val, x, y->son[0]);
x->maintain(); y->maintain();
}
node *merge(node *x, node *y) {
if (!x || !y) return x ? x : y;
if (x->_rand < y->_rand) {
node *r = copynode(x);
r->son[1] = merge(r->son[1], y);
r->maintain(); return r;
}
else {
node *r = copynode(y);
r->son[0] = merge(x, r->son[0]);
r->maintain(); return r;
}
}
node *merge(node *x, node *y, node *z) {
return merge(merge(x, y), z);
}
void insert(node *p, int val) {
split(p, val, a, b);
d = new node(val);
c = merge(a, d, b);
root.push_back(c);
//c->print();
}
void erase(node *p, int val) {
split(p, val, a, b);
split(b, val + 1, b, c);
if (b == nl) return root.push_back(p);
b = merge(b->son[0], b->son[1]);
root.push_back(merge(a, b, c));
}
int find(node *p, int val) {
root.push_back(p);
int r = 0;
for (node *t = p; t; ) {
if (t->_value < val) {
r += t->son[0]->size() + 1;
t = t->son[1];
}
else t = t->son[0];
}
return r + 1;
}
int kth(node *p, int rank) {
root.push_back(p);
for (node *t = p; t; ) {
if (t->son[0]->size() + 1 == rank) return t->_value;
if (t->son[0]->size() >= rank) t = t->son[0];
else rank -= t->son[0]->size() + 1, t = t->son[1];
}
}
int pre(node *p, int val) {
root.push_back(p);
int r = -2147483647;
for (node *t = p; t; ) {
if (t->_value < val) {
r = t->_value;
t = t->son[1];
}else t = t->son[0];
}return r;
}
int nxt(node *p, int val) {
root.push_back(p);
int r = 2147483647;
for (node *t = p; t; ) {
if (t->_value > val) {
r = t->_value;
t = t->son[0];
}else t = t->son[1];
}return r;
}
}
  • 可持久化$Treap$(数组板$AC$)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
namespace Treap {
const int maxn = 5e5;
struct node {
int son[2], value, size, fix;
node() {}
node(int val = 0, bool e = false) {
fix = rand(); value = val; size = e; son[0] = son[1] = 0;
}
}T[maxn * 50];
int root[maxn], nodeCnt, rootCnt;
int copynode(int p) {
T[++nodeCnt] = T[p]; return nodeCnt;
}
int newnode(int val) {
T[++nodeCnt] = node(val, true); return nodeCnt;
}
void maintain(int p) {
if (p) T[p].size = T[T[p].son[0]].size + T[T[p].son[1]].size + 1;
}
void split(int p, int val, int &x, int &y) {
if (!p) return void(x = y = 0);
if (T[p].value < val)
x = copynode(p), split(T[p].son[1], val, T[x].son[1], y);
else
y = copynode(p), split(T[p].son[0], val, x, T[y].son[0]);
maintain(x); maintain(y);
}
int merge(int x, int y) {
if (!x || !y) return x + y;
if (T[x].fix < T[y].fix) {
int r = copynode(x);
T[r].son[1] = merge(T[x].son[1], y);
maintain(r); return r;
}
else {
int r = copynode(y);
T[r].son[0] = merge(x, T[y].son[0]);
maintain(r); return r;
}
}
int merge(int x, int y, int z) {
return merge(merge(x, y), z);
}
void insert(int p, int val) {
int a, b, c;
split(p, val, a, c);
b = newnode(val);
root[++rootCnt] = merge(a, b, c);
}
void erase(int p, int val) {
int a, b, c;
split(p, val, a, b);
split(b, val + 1, b, c);
b = merge(T[b].son[0], T[b].son[1]);
root[++rootCnt] = merge(a, b, c);
}
int find(int p, int val) {
root[++rootCnt] = p;
int r = 0;
while (p) {
if (T[p].value < val)
r += T[T[p].son[0]].size + 1, p = T[p].son[1];
else p = T[p].son[0];
}
return r + 1;
}
int kth(int p, int rank) {
root[++rootCnt] = p;
while (p) {
if (T[T[p].son[0]].size + 1 == rank) return T[p].value;
if (T[T[p].son[0]].size >= rank) p = T[p].son[0];
else rank -= 1 + T[T[p].son[0]].size, p = T[p].son[1];
}
}
int pre(int p, int val) {
root[++rootCnt] = p;
int r = -2147483647;
while (p)
if (T[p].value < val)
r = T[p].value, p = T[p].son[1];
else p = T[p].son[0];
return r;
}
int nxt(int p, int val) {
root[++rootCnt] = p;
int r = 2147483647;
while (p)
if (T[p].value > val)
r = T[p].value, p = T[p].son[0];
else p = T[p].son[1];
return r;
}
}
  • $splay$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
namespace Splay {
#define nl NULL
struct node {
node *father, *son[2];
int _value, _size, _count;
node(int val, node *f = nl) {
_value = val; _size = _count = 1;
father = f; son[0] = son[1] = nl;
}
int size() {
return this == nl ? 0 : _size;
}
bool who() {
return father->son[1] == this;
}
void maintain() {
_size = son[0]->size() + _count + son[1]->size();
}
}*root;
void rotate(node *t) {
node *f = t->father, *g = f->father;
bool a = t->who(), b = !a;
f->son[a] = t->son[b];
if (t->son[b])
t->son[b]->father = f;
t->father = g;
if (g)
g->son[f->who()] = t;
else
root = t;
t->son[b] = f;
f->father = t;
f->maintain();
t->maintain();
}
void splay(node *t, node *p) {
while (t->father != p) {
node *f = t->father;
if (f->father == p) rotate(t);
else if (t->who() ^ f->who())
rotate(t), rotate(t);
else rotate(f), rotate(t);
}
}
void insert(int val) {
if (!root) {
root = new node(val); return;
}
for (node *t = root; t; t = t->son[val > t->_value]) {
if (val == t->_value) {
splay(t, nl); t->_count++;
t->maintain(); return;
}
if (t->son[val > t->_value] == nl) {
bool a = val > t->_value;
t->son[a] = new node(val, t);
splay(t->son[a], nl); return;
}
}
}
void erase(int val) {
node *t = root;
while (t) {
if (t->_value == val) break;
t = t->son[val > t->_value];
}
if (!t) return;
splay(t, nl);
if (t->_count > 1) {
t->_count--; t->_size--; return;
}
if (t->son[0] == nl) {
root = t->son[1];
if (root)
root->father = nl;
delete t; return;
}
node *p = t->son[0];
while (p->son[1])
p = p->son[1];
splay(p, t);
root = p;
p->father = nl;
p->son[1] = t->son[1];
if (t->son[1])
t->son[1]->father = p;
p->maintain(); delete t;
}
int find(int val) {
for (node *t = root; t; t = t->son[val > t->_value])
if (t->_value == val) { splay(t, nl); break; }
return root->son[0]->size() + 1;
}
int kth(int rank) {
for (node *t = root; t;) {
if (t->son[0]->size() < rank && t->son[0]->size() + t->_count >= rank) return t->_value;
if (t->son[0]->size() >= rank) t = t->son[0];
else rank -= t->son[0]->size() + t->_count, t = t->son[1];
}
}
int pre(int val) {
int r = 0;
for (node *t = root; t;) {
if (t->_value < val) {
r = t->_value;
t = t->son[1];
}else t = t->son[0];
}return r;
}
int nxt(int val) {
int r = 0;
for (node *t = root; t;) {
if (t->_value > val) {
r = t->_value;
t = t->son[0];
}else t = t->son[1];
}return r;
}
void print() {
printf("#");
for (int i = 1; i <= root->size(); i++)
printf(" %d #", kth(i));
printf("\n");
}
}

$LinkCut-Tree$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
namespace lct {
struct node {
node *father, *son[2];
int value, sum; bool rev;
node(int val = 0) {
value = val; sum = val; rev = false;
son[0] = son[1] = father = nl;
}
bool is_root() {
if (!father) return true;
return father->son[0] != this && father->son[1] != this;
}
bool who() {
return father->son[1] == this;
}
void reverse() {
swap(son[0], son[1]); rev = !rev;
}
void pushdown_once() {
if (!rev) return; rev = false;
if (son[0]) son[0]->reverse();
if (son[1]) son[1]->reverse();
}
void pushdown() {
if (!is_root()) father->pushdown(); pushdown_once();
}
void maintain() {
sum = value;
if (son[0]) sum += son[0]->sum;
if (son[1]) sum += son[1]->sum;
}
void rotate() {
node *f = father, *g = f->father;
bool a = who(), b = !a;
f->son[a] = son[b];
if (son[b])
son[b]->father = f;
son[b] = f;
father = g;
if (!f->is_root())
g->son[f->who()] = this;
f->father = this;
f->maintain(); maintain();
}
void splay() {
for (pushdown(); !is_root(); rotate())
if (!father->is_root())
if (who() ^ father->who()) rotate();
else father->rotate();
}
void access() {
for (node *y = nl, *x = this; x; y = x, x = x->father)
x->splay(), x->son[1] = y, x->maintain();
}
void make_root() {
access(); splay(); reverse();
}
node *root() {
access(); splay();
for (node *x = this; ; x = x->son[0])
if (!x->son[0]) return x;
}
}*T[maxn];
bool con(int x, int y) {
return T[x]->root() == T[y]->root();
}
void link(int x, int y) {
T[x]->make_root(); T[x]->father = T[y];
}
void cut(int x, int y) {
T[x]->make_root(); T[y]->access(); T[y]->splay();
T[x]->father = T[y]->son[0] = nl; T[y]->maintain();
}
void change(int x, int y) {
T[x]->splay(); T[x]->value = y; T[x]->maintain();
}
int query(int x, int y) {
T[x]->make_root(); T[y]->access();
T[x]->splay(); return T[x]->sum;
}
}

字符串

$hash$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef std::pair<unsigned long long, unsigned long long> pull;
#define A first
#define B second
namespace Hash{
pull Pow[250]; unsigned long long base = 127, Mod1 = 1e9 + 7, Mod2 = 1e9 + 9;
void init(int l) {
Pow[l - 1].A = Pow[l - 1].B = 1;
for (int i = l - 2; i >= 0; --i)
Pow[i].A = Pow[i + 1].A * base % Mod1,
Pow[i].B = Pow[i + 1].B * base % Mod2;
}
pull hash(char *s) {
pull ans(0, 0);
for (int i = 0; s[i]; ++i)
ans.A = (ans.A * base + s[i]) % Mod1,
ans.B = (ans.B * base + s[i]) % Mod2;
return ans;
}
pull hash(pull now, int p, char *s) {
now.A = (now.A + Mod1 - s[p] * Pow[p].A % Mod1) % Mod1;
now.B = (now.B + Mod2 - s[p] * Pow[p].B % Mod2) % Mod2;
return now;
}
}

马拉车

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
namespace manacher {
int maxR[maxn];
char t[maxn];
int deal(char *s, int n) {
int m = 0; t[m] = '$'; t[++m] = '#';
for (int i = 0; i < n; i++)
t[++m] = s[i], t[++m] = '#';
t[++m] = '&';
int mid = 0, R = 0;
for (int i = 1; i <= m; i++) {
if (i <= R) maxR[i] = std::min(maxR[mid * 2 - i], R - i);
while (t[i - maxR[i] - 1] == t[i + maxR[i] + 1]) maxR[i]++;
if (i + maxR[i] > R) R = i + maxR[i], mid = i;
}
int ans = 0;
for (int i = 1; i < m; i ++)
ans = Mod(ans + ((maxR[i] + 1) >> 1));
return ans;
}
}

后缀数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
namespace Suffix {
int SA[maxn], Rank[maxn], Height[maxn], str[maxn], tmp[maxn], Tax[maxn];
void init(int n) {
for (int i = 1; i <= n; i++) scanf("%d", &str[i]);
}
void sort(int n, int m) {
for (int i = 0; i <= m; i++) Tax[i] = 0;
for (int i = 1; i <= n; i++) Tax[Rank[i]]++;
for (int i = 1; i <= m; i++) Tax[i] += Tax[i - 1];
for (int i = n; i; i--) SA[Tax[Rank[tmp[i]]]--] = tmp[i];
}
bool cmp(int *f, int x, int y, int w, int n) {
return f[x] == f[y] && (x + w > n ? 0 : f[x + w]) == (y + w > n ? 0 : f[y + w]);
}
void build(int n) {
init(n);
for (int i = 1; i <= n; i++) Rank[i] = str[i], tmp[i] = i;
int m = 1000; sort(n, m);
for (int i, w = 1, p = 1; p < n; m = p, w <<= 1) {
for (p = 0, i = n - w + 1; i <= n; i++) tmp[++p] = i;
for (i = 1; i <= n; i++) if (SA[i] > w) tmp[++p] = SA[i] - w;
sort(n, m); std::swap(Rank, tmp); Rank[SA[1]] = p = 1;
for (i = 2; i <= n; i++) Rank[SA[i]] = cmp(tmp, SA[i], SA[i - 1], w, n) ? p : ++p;
}
int j, k = 0;
for (int i = 1; i <= n; Height[Rank[i]] = k, i++)
for (k = (k ? k - 1 : k), j = SA[Rank[i] - 1]; str[i + k] == str[j + k]; k++);
}
}

后缀自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
namespace SuffixAutomation {
struct node {
int minlen, maxlen, trans[26], slink;
}T[maxn]; int nodeCnt;
int newnode(int maxlen, int minlen, int* trans, int slink) {
T[nodeCnt].maxlen = maxlen;
T[nodeCnt].minlen = minlen;
T[nodeCnt].slink = slink;
if (trans != NULL)
for (int i = 0; i < 26; i++) T[nodeCnt].trans[i] = trans[i];
else
for (int i = 0; i < 26; i++) T[nodeCnt].trans[i] = -1;
return nodeCnt++;
}
int addchar(char ch, int u) {
int c = ch - 'a', v = u;
int z = newnode(T[u].maxlen + 1, -1, NULL, -1);
while (v != -1 && T[v].trans[c] == -1)
T[v].trans[c] = z, v = T[v].slink;
if (v == -1) {
T[z].minlen = 1; T[z].slink = 0; return z;
}
int x = T[v].trans[c];
if (T[v].maxlen + 1 == T[x].maxlen) {
T[z].slink = x; T[z].minlen = T[x].maxlen + 1; return z;
}
int y = newnode(T[v].maxlen + 1, -1, T[x].trans, T[x].slink);
T[z].minlen = T[x].minlen = T[y].maxlen + 1;
T[z].slink = T[x].slink = y;
int w = v;
while (w != -1 && T[w].trans[c] == x)
T[w].trans[c] = y, w = T[w].slink;
T[y].minlen = T[T[y].slink].maxlen + 1;
return z;
}
void build(char *s) {
newnode(0, 0, 0, -1);
for (int i = 0, j = 0; s[i]; i++)
j = addchar(s[i], j);
}
}

图论

最短路

  • $floyd$ 多源最短路 & 最短路径计数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int maxn = 300 + 10;
int dis[maxn][maxn], way[maxn][maxn];
void init() {
memset(dis, 63, sizeof(dis));
}
void add(int x, int y, int z) {
dis[x][y] = dis[y][x] = std::min(dis[x][y], z);
way[x][y] = way[y][x] = 1;
}
void floyd(int n) {
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (dis[i][j] == dis[i][k] + dis[k][j])
way[i][j] += way[i][k] * way[k][j];
else if (dis[i][j] > dis[i][k] + dis[k][j]){
dis[i][j] = dis[i][k] + dis[k][j];
way[i][j] = way[i][k] * way[k][j];
}
}
  • $spfa$ 单源最短路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void spfa(int s){
queue<int>q;
for(int i = 1; i <= size; i++) dis[i] = INT_MAX;
dis[s] = 0; q.push(s);
while(q.size()){
int u = q.front(); q.pop(); inq[u] = false;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to;
if(dis[v] - dis[u] > e[i].dis){
dis[v] = dis[u] + e[i].dis;
if(!inq[v]) inq[v] = true, q.push(v);
}
}
}
}
  • $dijkstra$ 单源最短路径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dijkstra(int s){
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
q.push(make_pair(0, s));
for(int i = 1; i <= size; i++) dis[i] = INF_MAX;
dis[s] = 0;
while(q.size()){
int u = q.top().second; q.pop();
if(vis[u]) continue; vis[u] = true;
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].to; if(vis[v]) continue;
if(dis[v] - dis[u] > e[i].dis){
dis[v] = dis[u] + e[i].dis;
q.push(make_pair(dis[v], v));
}
}
}
}

最小生成树

  • $kruskal$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct edge { int a, b, w; };
bool cmpedge(edge x, edge y) { return x.w < y.w; }
std::vector<edge>e;
int kruskal(int n) {
mergefindSet s; s.clear(n);
int ans = 0, block = n;
std::sort(e.begin(), e.end(), cmpedge);
for (int i = 0; i < e.size(); i++) {
int a = e[i].a, b = e[i].b;
if (s.find(a) == s.find(b)) continue;
ans += e[i].w; s.merge(a, b);
block = ~-block; if (block == 1) return ans;
}
return -1;
}
  • $prim$

网络流

  • $dinic$ 网络流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
namespace MaxFlow {
const int maxm = 1e5 + 10;
const int maxn = 1e4 + 10;
const int inf = 1e9;
struct edge {
int to, next, cap;
edge() {}
edge(int x, int y, int z) {
to = x; next = y; cap = z;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
int deep[maxn];
void add(int x, int y, int w) {
e[++edgeCnt] = edge(y, head[x], w); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0); head[y] = edgeCnt;
}
bool bfs(int s, int t) {
memset(deep, 0, sizeof(int) * (t + 1));
std::queue<int>q; q.push(s); deep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v]) continue;
deep[v] = deep[u] + 1; q.push(v);
}
}
return deep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v] != deep[u] + 1) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, inf);
return r;
}
}
  • $zkw$ 最小费用最大流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
namespace MinCostMaxFlow {
const int maxm = 2e5;
const int maxn = 2e4;
const int inf = 1e9;
struct edge {
int to, next, cap, dis;
edge(){}
edge(int x, int y, int z, int w) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool inq[maxn], vis[maxn];
bool spfa(int s, int t) {
//memset(dis, -1, sizeof(int) * (t + 1));
memset(dis, -1, sizeof(dis));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (!~dis[v] || dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != -1;
}
int dfs(int u, int t, int f) {
vis[u] = true; if (u == t || !f) return f; int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(e[i].cap, f));
e[i].cap -= a; e[i ^ 1].cap += a; f -= a; r += a;
}
return r;
}
std::pair<int,int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (spfa(s, t)) {
memset(vis, false, sizeof(vis));
tmp = dfs(s, t, inf);
flow += tmp; cost += tmp * dis[s];
}
return std::make_pair(flow, cost);
}
}

计算几何

基本运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
namespace geometry {
const double ee = 1e-9;
const double oo = 1e15;
char tmp;
bool equ(double x, double y) {
return fabs(x - y) <= ee;
}
struct vec {
double x, y;
vec() { x = y = 0; }
vec(double x, double y) : x(x), y(y) {}
void read() {
std::cin >> tmp >> x >> tmp >> y >> tmp;
}
};
struct seg {
vec a, b;
seg() {}
seg(vec a, vec b) : a(a), b(b) {}
};
vec operator + (vec a, vec b) {
return vec(a.x + b.x, a.y + b.y);
}
vec operator - (vec a, vec b) {
return vec(a.x - b.x, a.y - b.y);
}
vec operator * (vec a, double b) {
return vec(a.x * b, a.y * b);
}
vec operator * (double b, vec a) {
return vec(a.x * b, a.y * b);
}
vec operator / (vec a, double b) {
return vec(a.x / b, a.y / b);
}
bool operator == (vec a, vec b) {
return equ(a.x, b.x) && equ(a.y, b.y);
}
double operator * (vec a, vec b) {
return a.x * b.x + a.y * b.y;
}
double operator ^ (vec a, vec b) {
return a.x * b.y - a.y * b.x;
}
double dis(vec a, vec b) {
return sqrt((a - b) * (a - b));
}
bool ptInRect(vec p, seg l) {
vec a = l.a, b = l.b;
if (p.x > std::max(a.x, b.x)) return false;
if (p.x < std::min(a.x, b.x)) return false;
if (p.y > std::max(a.y, b.y)) return false;
if (p.y < std::min(a.y, b.y)) return false;
return true;
}
bool ptOnSeg(vec p, seg l) {
return equ((l.a - l.b) ^ p, 0) && ptInRect(p, l);
}
bool segCntLine(seg s, seg l) {
return ((s.a - l.a) ^ (l.b - l.a)) * ((s.b - l.a) ^ (l.b - l.a)) >= 0;
}
bool segCrossSeg(seg l1, seg l2) {
if (!ptInRect(l1.a, l2)) return false;
if (!ptInRect(l1.b, l2)) return false;
if (!segCntLine(l1, l2)) return false;
if (!segCntLine(l2, l1)) return false;
return true;
}
}

数学基础

付费通(fft)快速离散卷积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct cpx {
double r, i; cpx() {}
cpx(double r, double i) :
r(r), i(i) {}
friend cpx operator * (cpx a, cpx b)
{ return cpx(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r); }
friend cpx operator + (cpx a, cpx b)
{ return cpx(a.r + b.r, a.i + b.i); }
friend cpx operator - (cpx a, cpx b)
{ return cpx(a.r - b.r, a.i - b.i); }
friend cpx operator / (cpx a, double b)
{ return cpx(a.r / b, a.i / b); }
};
namespace FFT {
int rev[maxn];
const double pi = acos(-1);
void fft(cpx *a, int n, int dft) {
for (int i = 0; i < n; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
for (int i = 1; i < n; i <<= 1) {
cpx rotate(cos(pi / i), dft * sin(pi / i));
for (int j = 0; j < n; j += (i << 1)) {
cpx x(1, 0);
for (int k = j; k < j + i; k++) {
cpx a1 = a[k], a2 = a[k + i];
a[k] = a1 + a2 * x; a[k + i] = a1 - a2 * x;
x = x * rotate;
}
}
}
}
void convolution(cpx *f, cpx *g, int n, int m) {
int s = 2, b = 1;
while (s < m + n - 1) s <<= 1, b++;
for (int i = 0; i < s; i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (b - 1));
fft(f, s, 1);
fft(g, s, 1);
for (int i = 0; i < s; i++) f[i] = f[i] * g[i];
fft(f, s, -1);
for (int i = 0; i < s; i++) f[i] = f[i] / s;
}
}

$NTT$快速数论卷积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
namespace NTT {
const int P = (479 << 21) + 1, G = 3;
inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { ll r = ll(x) * y; return r >= P ? int(r % P) : int(r); }
inline int pow(int x, int y, int ans = 1) {
while (y) {
if (y & 1) ans = mul(ans, x);
y >>= 1, x = mul(x, x);
}return ans;
}
int rev[maxn];
void ntt(int *a, int n, int f) {
for (int i = 0; i < n; i++) if (i < rev[i]) std::swap(a[i], a[rev[i]]);
for (int i = 1; i < n; i <<= 1) {
int e = pow(f, (P - 1) / (i << 1));
for (int j = 0; j < n; j += (i << 1)) {
int x = 1;
for (int k = j; k < j + i; k++) {
int a1 = a[k], a2 = mul(x, a[k + i]);
a[k] = pls(a1, a2); a[k + i] = dec(a1, a2);
x = mul(x, e);
}
}
}
}
void convolution(int *f, int *g, int n, int m) {
int s = 2, b = 1; while (s < n + m - 1) s <<= 1, b++;
for (int i = 0; i < s; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (b - 1));
ntt(f, s, G); ntt(g, s, G);
for (int i = 0; i < s; i++) f[i] = mul(f[i], g[i]);
ntt(f, s, pow(G, P - 2)); int inv = pow(s, P - 2);
for (int i = 0; i < s; i++) f[i] = mul(f[i], inv);
}
}

附表:用到的各种素数及其原根

$r*2^k+1$ r k g
3 1 1 2
5 1 2 2
17 1 4 3
97 3 5 5
193 3 6 5
257 1 8 3
7681 15 9 17
12289 3 12 11
40961 5 13 3
65537 1 16 3
786433 3 18 10
5767169 11 19 3
7340033 7 20 3
23068673 11 21 3
104857601 25 22 3
167772161 5 25 3
469762049 7 26 3
998244353 119 23 3
1004535809 479 21 3
2013265921 15 27 31
2281701377 17 27 3
3221225473 3 30 5
75161927681 35 31 3
77309411329 9 33 7
206158430209 3 36 22
2061584302081 15 37 7
2748779069441 5 39 3
6597069766657 3 41 5
39582418599937 9 42 5
79164837199873 9 43 5
263882790666241 15 44 7
1231453023109121 35 45 3
1337006139375617 19 46 3
3799912185593857 27 47 5
4222124650659841 15 48 19
7881299347898369 7 50 6
31525197391593473 7 52 3
180143985094819841 5 55 6
1945555039024054273 27 56 5
4179340454199820289 29 57 3

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2018 Anoxiacxy All Rights Reserved.

UV : | PV :