NOI 前的代码模版整理及复习

想着熟练版子的同时就都整理出来好了,于是就有了这个。。。码风较平时会好看一些。

代码头注释中的英文纯属口胡(尤其是上下界网络流那块)。

目前能想到的就这些了。。。坐等 NOI 滚粗。

UPD: 里面不少代码有误,请移步 Pepcy’s Templates for OI and ACM-ICPC

目录

1 数据结构

1.1 线段树

1.2 树链剖分

1.3 Splay

1.4 Treap

1.5 Link-Cut Tree

1.6 主席树(链/树)

1.7 可持久化 Treap

1.8 并查集

1.9 稀疏表

2 图与树

2.1 单源最短路

2.2 Floyd

2.3 网络流

2.4 费用流

2.5 无源无汇上下界可行流

2.6 有源有汇上下界最大流

2.7 有源有汇上下界最小流

2.8 Tarjan

2.9 虚树

3 字符串

3.1 后缀数组

3.2 后缀自动机

3.3 AC 自动机

3.4 Manacher

3.5 回文树

3.6 KMP

4 数学

4.1 欧拉筛

4.2 线性基

4.3 高斯消元

4.4 FFT/NTT

4.5 线性预处理逆元

4.6 组合数预处理与 Lucas 定理

5 其他/不会分类

5.1 三维偏序


数据结构

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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
/*
* Algorithm template : Segment Tree
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>
#include <algorithm>

const int MAXN = 100005;

struct SegT {
struct Node {
int l, r;
Node *lc, *rc;
long long sum, tag;

Node() {}
Node(int pos, int val) : l(pos), r(pos), sum(val), tag(0), lc(NULL), rc(NULL) {}
Node(Node *lc, Node *rc) : l(lc->l), r(rc->r), lc(lc), rc(rc), tag(0) {
maintain();
}

void add(long long d) {
sum += (r - l + 1) * d;
tag += d;
}

void pushDown() {
if (tag) {
lc->add(tag);
rc->add(tag);
tag = 0;
}
}

void maintain() {
sum = lc->sum + rc->sum;
}

void update(int l, int r, int d) {
if (r < this->l || this->r < l) return;
if (l <= this->l && this->r <= r) {
add(d);
return;
}
pushDown();
lc->update(l, r, d), rc->update(l, r, d);
maintain();
}

long long query(int l, int r) {
if (r < this->l || this->r < l) return 0;
if (l <= this->l && this->r <= r) return sum;
pushDown();
return lc->query(l, r) + rc->query(l, r);
}
} *root, _pool[MAXN << 1], *_curr;

SegT() : root(NULL), _curr(_pool) {}

Node *_build(int l, int r, int *a) {
if (l == r) return new (_curr++) Node(l, a[l]);
int mid = l + ((r - l) >> 1);
return new (_curr++) Node(_build(l, mid, a), _build(mid + 1, r, a));
}
void build(int l, int r, int *a) {
root = _build(l, r, a);
}

void update(int l, int r, int d) {
root->update(l, r, d);
}

long long query(int l, int r) {
return root->query(l, r);
}
} segT;

int main() {
int n;
scanf("%d", &n);

static int a[MAXN];
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

segT.build(1, n, a);

int q;
scanf("%d", &q);
while (q--) {
int op, l, r;
scanf("%d %d %d", &op, &l, &r);

if (op == 1) {
int d;
scanf("%d", &d);
segT.update(l, r, d);
} else {
printf("%lld\n", segT.query(l, r));
}
}

return 0;
}

树链剖分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
/*
* Algorithm template : Heavy-light Decomposition
*
* by: Pepcy_Ch
* time: 2017.7.10
*/

#include <cstdio>
#include <climits>
#include <algorithm>

const int MAXN = 100005;

struct Node;
struct Edge;
struct Chain;

struct Node {
Edge *e;
Chain *c;
Node *max, *fa;
int dfn, dfnR, dep, size, val; // use dfnR when there're operations on sub-trees
} N[MAXN];

struct Edge {
Node *u, *v;
Edge *next;

Edge() {}
Edge(Node *u, Node *v) : u(u), v(v), next(u->e) {}
} _poolE[MAXN << 1], *_currE = _poolE;
void addEdge(int u, int v) {
N[u].e = new (_currE++) Edge(&N[u], &N[v]);
N[v].e = new (_currE++) Edge(&N[v], &N[u]);
}

struct Chain {
Node *top;

Chain(Node *top = NULL) : top(top) {}
} _poolC[MAXN], *_currC = _poolC;

void dfs1(Node *u) {
u->size = 1;

for (Edge *e = u->e; e; e = e->next) if (e->v != u->fa) {
e->v->dep = u->dep + 1;
e->v->fa = u;

dfs1(e->v);

u->size += e->v->size;
if (!u->max || u->max->size < e->v->size) u->max = e->v;
}
}
void dfs2(Node *u, Node *fa = NULL) {
static int dfsClock = 0;
u->dfn = ++dfsClock;

if (!u->fa || u->fa->max != u) u->c = new (_currC++) Chain(u);
else u->c = u->fa->c;

if (u->max) dfs2(u->max);

for (Edge *e = u->e; e; e = e->next) if (e->v != u->fa && e->v != u->max) dfs2(e->v);

u->dfnR = dfsClock;
}
void split() {
N[1].dep = 1;
dfs1(&N[1]);
dfs2(&N[1]);
}

struct SegT {
struct Node {
int l, r;
Node *lc, *rc;
int max, tag;

Node() {}
Node(int l, int r, int val) : l(l), r(r), max(val), tag(0), lc(NULL), rc(NULL) {}
Node(int l, int r, Node *lc, Node *rc) : l(l), r(r), lc(lc), rc(rc), tag(0) {
maintain();
}

void add(int d) {
max += d;
tag += d;
}

void pushDown() {
if (tag) {
if (lc) lc->add(tag);
if (rc) rc->add(tag);
tag = 0;
}
}

void maintain() {
max = std::max(lc ? lc->max : INT_MIN, rc ? rc->max : INT_MIN);
}

void update(int l, int r, int d) {
if (l > this->r || this->l > r) return;
if (l <= this->l && this->r <= r) {
add(d);
return;
}
pushDown();
lc->update(l, r, d), rc->update(l, r, d);
maintain();
}

int query(int l, int r) {
if (l > this->r || this->l > r) return INT_MIN;
if (l <= this->l && this->r <= r) return max;
pushDown();
return std::max(lc->query(l, r), rc->query(l, r));
}
} *root, _pool[MAXN << 1], *_curr;

SegT() : root(NULL), _curr(_pool) {}

Node *_build(int l, int r, int *a) {
if (l > r) return NULL;
if (l == r) return new (_curr++) Node(l, r, a[l]);
int mid = l + (r - l) / 2;
return new (_curr++) Node(l, r, _build(l, mid, a), _build(mid + 1, r, a));
}
void build(int l, int r, int *a) {
root = _build(l, r, a);
}

void update(int l, int r, int d) {
root->update(l, r, d);
}

int query(int l, int r) {
return root->query(l, r);
}
} segT;

void update(int a, int b, int d) {
Node *u = &N[a], *v = &N[b];

while (u->c != v->c) {
if (u->c->top->dep < v->c->top->dep) std::swap(u, v);
segT.update(u->c->top->dfn, u->dfn, d);
u = u->c->top->fa;
}

if (u->dep > v->dep) std::swap(u, v);
segT.update(u->dfn, v->dfn, d);
}

int query(int a, int b) {
Node *u = &N[a], *v = &N[b];
int res = INT_MIN;

while (u->c != v->c) {
if (u->c->top->dep < v->c->top->dep) std::swap(u, v);
res = std::max(res, segT.query(u->c->top->dfn, u->dfn));
u = u->c->top->fa;
}

if (u->dep > v->dep) std::swap(u, v);
res = std::max(res, segT.query(u->dfn, v->dfn));

return res;
}

int main() {
int n;
scanf("%d", &n);

for (int i = 1; i <= n; i++) scanf("%d", &N[i].val);

for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
addEdge(u, v);
}

split();

static int temp[MAXN];
for (int i = 1; i <= n; i++) temp[N[i].dfn] = N[i].val;
segT.build(1, n, temp);

int q;
scanf("%d", &q);

while (q--) {
int op, u, v;
scanf("%d %d %d", &op, &u, &v);
if (op == 1) {
int d;
scanf("%d", &d);
update(u, v, d);
} else printf("%d\n", query(u, v));
}

return 0;
}

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
/*
* Algorithm template : Splay
*
* by: Pepcy_Ch
* time: 2017.7.13
*/

#include <cstdio>
#include <climits>
#include <algorithm>

const int MAXN = 100005;

template <typename T, size_t SIZE>
struct MemoryPool {
char mem[SIZE * sizeof (T)], *memTop, *del[SIZE], **delTop;

MemoryPool() : memTop(mem), delTop(del) {}

void *alloc() {
if (delTop != del) return (void *) *--delTop;
char *res = memTop;
memTop += sizeof (T);
return (void *) res;
}

void free(void *p) {
*delTop++ = (char *) p;
}
};

struct Splay {
struct Node {
Node *c[2], *fa, **root;
int val, cnt, size;
static MemoryPool<Node, MAXN> pool;

Node() {}
Node(Node **root, Node *fa, int val) : val(val), size(1), cnt(1), c(), fa(fa), root(root) {}

~Node() {
if (c[0]) delete c[0];
if (c[1]) delete c[1];
}

void *operator new(size_t) {
return pool.alloc();
}

void operator delete(void *p) {
pool.free(p);
}

void maintain() {
size = (c[0] ? c[0]->size : 0) + cnt + (c[1] ? c[1]->size : 0);
}

int relation() {
return fa->c[1] == this;
}

void rotate() {
Node *o = fa;
int x = relation();

fa = o->fa;
if (fa) fa->c[o->relation()] = this;

o->c[x] = c[x ^ 1];
if (c[x ^ 1]) c[x ^ 1]->fa = o;

c[x ^ 1] = o;
o->fa = this;

o->maintain();
maintain();

if (!fa) *root = this;
}

Node *splay(Node *targetFa = NULL) {
while (fa != targetFa) {
if (fa->fa == targetFa) rotate();
else if (relation() == fa->relation()) fa->rotate(), rotate();
else rotate(), rotate();
}
return this;
}

Node *pred() {
Node *u = c[0];
while (u->c[1]) u = u->c[1];
return u;
}

Node *succ() {
Node *u = c[1];
while (u->c[0]) u = u->c[0];
return u;
}
} *root;

Splay() : root(NULL) {}

static int size(const Node *u) {
return u ? u->size : 0;
}

void init() {
insert(INT_MIN);
insert(INT_MAX);
}

Node *insert(int val) {
Node **u = &root, *fa = NULL;

while (*u && (*u)->val != val) {
fa = *u;
fa->size++;
u = &(*u)->c[val > (*u)->val];
}

if (*u) {
(*u)->cnt++;
(*u)->size++;
} else {
(*u) = new Node(&root, fa, val);
}

return (*u)->splay();
}

void erase(Node *u) {
Node *pred = u->pred(), *succ = u->succ();
pred->splay();
succ->splay(pred);

if (u->cnt > 1) {
u->cnt--;
u->size--;
} else {
delete succ->c[0];
succ->c[0] = NULL;
}

pred->size--;
succ->size--;
}
void erase(int val) {
Node *u = find(val);
if (u) erase(u);
}

Node *find(int val) {
Node *u = root;
while (u && u->val != val) u = u->c[val > u->val];
if (u) return u->splay();
else return NULL;
}

Node *select(int k) {
Node *u = root;
while (k < size(u->c[0]) || k >= size(u->c[0]) + u->cnt) {
if (k < size(u->c[0])) u = u->c[0];
else {
k -= size(u->c[0]) + u->cnt;
u = u->c[1];
}
}
return u->splay();
}

int rank(int val) {
Node *u = find(val);
if (!u) {
u = insert(val);
int res = size(u->c[0]);
erase(u);
return res;
}
return size(u->c[0]);
}

int pred(int val) {
Node *u = find(val);
if (!u) {
u = insert(val);
int res = u->pred()->val;
erase(u);
return res;
}
return u->pred()->val;
}

int succ(int val) {
Node *u = find(val);
if (!u) {
u = insert(val);
int res = u->succ()->val;
erase(u);
return res;
}
return u->succ()->val;
}
} splay;

MemoryPool<Splay::Node, MAXN> Splay::Node::pool;

int main() {
splay.init();

int n;
scanf("%d", &n);

while (n--) {
int op, x;
scanf("%d %d", &op, &x);

if (op == 1) splay.insert(x);
if (op == 2) splay.erase(x);
if (op == 3) printf("%d\n", splay.rank(x));
if (op == 4) printf("%d\n", splay.select(x)->val);
if (op == 5) printf("%d\n", splay.pred(x));
if (op == 6) printf("%d\n", splay.succ(x));
}

return 0;
}

Treap

文艺平衡树代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/*
* Algorithm template : Treap
*
* by: Pepcy_Ch
* time: 2017.7.13
*/

#include <cstdio>
#include <cstdlib>
#include <algorithm>

const int MAXN = 100005;

struct Treap {
struct Node {
Node *lc, *rc;
int val, size;
bool rev;

Node() {}
Node(int val, Node *lc = NULL, Node *rc = NULL) : val(val), lc(lc), rc(rc), rev(false) {
maintain();
}

void reverse() {
std::swap(lc, rc);
rev ^= 1;
}

void pushDown() {
if (rev) {
if (lc) lc->reverse();
if (rc) rc->reverse();
rev = false;
}
}

void maintain() {
size = (lc ? lc->size : 0) + 1 + (rc ? rc->size : 0);
}

void print() {
pushDown();
if (lc) lc->print();
printf("%d ", val);
if (rc) rc->print();
}
} *root, _pool[MAXN], *_curr;

Treap() : root(NULL), _curr(_pool) {}

static int size(const Node *u) {
return u ? u->size : 0;
}

Node *_build(int l, int r) {
if (l > r) return NULL;
int mid = l + (r - l) / 2;
return new (_curr++) Node(mid, _build(l, mid - 1), _build(mid + 1, r));
}
void build(int l, int r) {
root = _build(l, r);
}

Node *merge(Node *a, Node *b) {
if (!a) return b;
if (!b) return a;

if (rand() % (a->size + b->size) < a->size) {
a->pushDown();
a->rc = merge(a->rc, b);
a->maintain();
return a;
} else {
b->pushDown();
b->lc = merge(a, b->lc);
b->maintain();
return b;
}
}

std::pair<Node *, Node *> split(Node *u, int pos) {
std::pair<Node *, Node *> res(NULL, NULL);
if (!u) return res;
u->pushDown();
if (pos <= size(u->lc)) {
res = split(u->lc, pos);
u->lc = res.second;
u->maintain();
res.second = u;
} else {
res = split(u->rc, pos - size(u->lc) - 1);
u->rc = res.first;
u->maintain();
res.first = u;
}
return res;
}

void reverse(int l, int r) {
std::pair<Node *, Node *> L = split(root, l - 1);
std::pair<Node *, Node *> R = split(L.second, r - l + 1);
R.first->reverse();
root = merge(merge(L.first, R.first), R.second);
}

void print() {
root->print();
puts("");
}
} treap;

int main() {
int n, m;
scanf("%d %d", &n, &m);

treap.build(1, n);

for (int i = 0, l, r; i < m; i++) {
scanf("%d %d", &l, &r);
treap.reverse(l, r);
}

treap.print();

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
* Algorithm template : Link-Cut Tree
*
* by: Pepcy_Ch
* 2017.7.13
*/

#include <cstdio>
#include <algorithm>

const int MAXN = 30005;

struct LinkCutTree {
struct Node {
Node *c[2], *fa, *pathFa;
int val, max;
bool rev;

Node() {}
Node(int val) : val(val), max(val), rev(false), fa(NULL), pathFa(NULL), c() {}

int relation() {
return fa->c[1] == this;
}

void maintain() {
max = val;
if (c[0]) max = std::max(max, c[0]->max);
if (c[1]) max = std::max(max, c[1]->max);
}

void pushDown() {
if (rev) {
std::swap(c[0], c[1]);
if (c[0]) c[0]->rev ^= 1;
if (c[1]) c[1]->rev ^= 1;
rev = false;
}
}

void rotate() {
std::swap(pathFa, fa->pathFa);

Node *o = fa;
int x = relation();

fa = o->fa;
if (fa) fa->c[o->relation()] = this;

o->c[x] = c[x ^ 1];
if (c[x ^ 1]) c[x ^ 1]->fa = o;

c[x ^ 1] = o;
o->fa = this;

o->maintain();
maintain();
}

void splay() {
while (fa) {
if (fa->fa) fa->fa->pushDown();
fa->pushDown();
pushDown();

if (!fa->fa) rotate();
else if (fa->relation() == relation()) fa->rotate(), rotate();
else rotate(), rotate();
}
}

void evert() {
access();
splay();
rev ^= 1;
}

void expose() {
splay();
pushDown();
if (c[1]) {
std::swap(c[1]->fa, c[1]->pathFa);
c[1] = NULL;
maintain();
}
}

bool splice() {
splay();
if (!pathFa) return false;

pathFa->expose();
pathFa->c[1] = this;
std::swap(fa, pathFa);
fa->maintain();
return true;
}

void access() {
expose();
while (splice());
}

int query() {
access();
splay();
return max;
}
} *N[MAXN], _pool[MAXN], *_curr;

LinkCutTree() : _curr(_pool) {}

void makeTree(int u, int val) {
N[u] = new (_curr++) Node(val);
}

void link(int u, int v) {
N[v]->evert();
N[v]->pathFa = N[u];
}

void cut(int u, int v) {
N[u]->evert();
N[v]->access();
N[v]->splay();
N[v]->pushDown();
N[v]->c[0]->fa = NULL;
N[v]->c[0] = NULL;
N[v]->maintain();
}

int query(int u, int v) {
N[u]->evert();
return N[v]->query();
}
} lct;

int main() {

return 0;
}

主席树

链上区间 $k$ 小值(为 POJ 2104 代码)。

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
/*
* Algorithm template : Segment kth Minimal/Maximum Number - Persistent Segment Tree
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>
#include <algorithm>

const int MAXN = 100005;

template <typename T, size_t SIZE>
struct MemoryPool {
char mem[SIZE * sizeof (T)], *top;

MemoryPool() : top(mem) {}

void *alloc() {
char *res = top;
top += sizeof (T);
return (void *) res;
}
};

struct PSegT {
struct Node {
Node *lc, *rc;
int cnt;
static MemoryPool<Node, MAXN * 20> pool;

Node(int cnt) : cnt(cnt), lc(NULL), rc(NULL) {}
Node(Node *lc = NULL, Node *rc = NULL)
: lc(lc), rc(rc), cnt((lc ? lc->cnt : 0) + (rc ? rc->cnt : 0)) {}

void *operator new(size_t) {
return pool.alloc();
}

void pushDown() {
if (lc && rc) return;
if (!lc) lc = new Node;
if (!rc) rc = new Node;
}

Node *insert(int l, int r, int val) {
if (val == l && val == r) return new Node(cnt + 1);
pushDown();
int mid = l + (r - l) / 2;
if (val <= mid) return new Node(lc->insert(l, mid, val), rc);
else return new Node(lc, rc->insert(mid + 1, r, val));
}

int rank() const {
return lc ? lc->cnt : 0;
}
} *root[MAXN];
int n;

PSegT() : root() {}

void build(int *a, int n) {
this->n = n;
root[0] = new Node;
for (int i = 1; i <= n; i++) root[i] = root[i - 1]->insert(1, n, a[i]);
}

int query(int l, int r, int k) {
Node *L = root[l - 1], *R = root[r];
int min = 1, max = n;
while (min < max) {
L->pushDown(), R->pushDown();
int mid = min + (max - min) / 2, temp = R->rank() - L->rank();
if (k <= temp) L = L->lc, R = R->lc, max = mid;
else L = L->rc, R = R->rc, k -= temp, min = mid + 1;
}
return min;
}
} pSegT;

MemoryPool<PSegT::Node, MAXN * 20> PSegT::Node::pool;

int main() {
int n, q;
scanf("%d %d", &n, &q);

static int a[MAXN], map[MAXN];
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

std::copy(a + 1, a + n + 1, map + 1);
std::sort(map + 1, map + n + 1);
int *end = std::unique(map + 1, map + n + 1);
for (int i = 1; i <= n; i++) a[i] = std::lower_bound(map + 1, end, a[i]) - map;

pSegT.build(a, n);

while (q--) {
int l, r, k;
scanf("%d %d %d", &l, &r, &k);
printf("%d\n", map[pSegT.query(l, r, k)]);
}

return 0;
}

树上两点间 $k$ 小值(为 BZOJ 2588 代码)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/*
* Algorithm template : kth Minimal/Maximum Number Between u and v - Persistent Segment Tree on Tree
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>
#include <climits>
#include <algorithm>

const int MAXN = 100005;
const int MAXN_LOG = 18;

template <typename T, size_t SIZE>
struct MemoryPool {
char mem[SIZE * sizeof (T)], *top;

MemoryPool() : top(mem) {}

void *alloc() {
char *res = top;
top += sizeof (T);
return (void *) res;
}
};

struct PSegT *null;
struct PSegT {
PSegT *lc, *rc;
int cnt;
static MemoryPool<PSegT, MAXN * 40> pool;

PSegT(int cnt) : cnt(cnt), lc(null), rc(null) {}
PSegT(PSegT *lc, PSegT *rc) : lc(lc), rc(rc), cnt(lc->cnt + rc->cnt) {}

void *operator new(size_t) {
return pool.alloc();
}

PSegT *insert(int l, int r, int val) {
if (val < l || val > r) return null;
if (val == l && val == r) return new PSegT(cnt + 1);
int mid = l + (r - l) / 2;
if (val <= mid) return new PSegT(lc->insert(l, mid, val), rc);
else return new PSegT(lc, rc->insert(mid + 1, r, val));
}
};
MemoryPool<PSegT, MAXN * 40> PSegT::pool;

struct Edge;
struct Node;

struct Node {
Edge *e;
PSegT *seg;
Node *f[MAXN_LOG];
int dep, val;
} N[MAXN];

struct Edge {
Node *u, *v;
Edge *next;

Edge() {}
Edge(Node *u, Node *v) : u(u), v(v), next(u->e) {}
} _pool[MAXN << 1], *_curr = _pool;
void addEdge(int u, int v) {
N[u].e = new (_curr++) Edge(&N[u], &N[v]);
N[v].e = new (_curr++) Edge(&N[v], &N[u]);
}

void init() {
null = new PSegT(0);
null->lc = null->rc = null;
}

void dfs(Node *u, bool init = true) {
if (init) {
u->f[0] = u;
u->dep = 1;
u->seg = null->insert(0, INT_MAX, u->val);
}

for (int i = 1; i < MAXN_LOG; i++) u->f[i] = u->f[i - 1]->f[i - 1];

for (Edge *e = u->e; e; e = e->next) if (e->v != u->f[0]) {
e->v->f[0] = u;
e->v->dep = u->dep + 1;
e->v->seg = u->seg->insert(0, INT_MAX, e->v->val);

dfs(e->v, false);
}
}

Node *lca(Node *u, Node *v) {
if (u->dep < v->dep) std::swap(u, v);

for (int i = MAXN_LOG - 1; ~i; i--) {
if (u->f[i]->dep >= v->dep) u = u->f[i];
}

for (int i = MAXN_LOG - 1; ~i; i--) {
if (u->f[i] != v->f[i]) {
u = u->f[i];
v = v->f[i];
}
}

return u == v ? u : u->f[0];
}

int query(int u, int v, int k) {
Node *p = lca(&N[u], &N[v]);
PSegT *su = N[u].seg, *sv = N[v].seg, *sp = p->seg, *sf = (p == p->f[0] ? null : p->f[0]->seg);

int l = 0, r = INT_MAX;
while (l < r) {
int mid = l + (r - l) / 2;
int temp = su->lc->cnt + sv->lc->cnt - sp->lc->cnt - sf->lc->cnt;
if (k <= temp) {
su = su->lc;
sv = sv->lc;
sp = sp->lc;
sf = sf->lc;
r = mid;
} else {
k -= temp;
su = su->rc;
sv = sv->rc;
sp = sp->rc;
sf = sf->rc;
l = mid + 1;
}
}
return l;
}

int main() {
init();

int n, q;
scanf("%d %d", &n, &q);

for (int i = 1; i <= n; i++) scanf("%d", &N[i].val);

for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
addEdge(u, v);
}

dfs(&N[1]);

int lastAns = 0;
while (q--) {
int u, v, k;
scanf("%d %d %d", &u, &v, &k);
u ^= lastAns;
printf("%d", lastAns = query(u, v, k));
q ? puts("") : 0;
}

return 0;
}

可持久化 Treap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
* Algorithm template : Persistent Treap
*
* by: Pepcy_Ch
* time: 2017.7.13
*/

#include <cstdio>
#include <cstdlib>
#include <algorithm>

const int MAXN = 100005;

struct PTreap {
struct Node {
Node *lc, *rc;
int val, size;

Node() {}
Node(int val, Node *lc, Node *rc)
: val(val), lc(lc), rc(rc), size((lc ? lc->size : 0) + 1 + (rc ? rc->size : 0)) {}
} *root, _pool[MAXN * 20], *_curr;

PTreap() : root(NULL), _curr(_pool) {}

static int size(const Node *u) {
return u ? u->size : 0;
}

Node *merge(Node *a, Node *b) {
if (!a) return b;
if (!b) return a;

if (rand() % (size(a) + size(b)) < size(a)) {
return new (_curr++) Node(a->val, a->lc, merge(a->rc, b));
} else {
return new (_curr++) Node(b->val, merge(a, b->lc), b->rc);
}
}

std::pair<Node *, Node *> split(Node *u, int pos) {
std::pair<Node *, Node *> res(NULL, NULL);
if (!u) return res;

if (pos <= size(u->lc)) {
res = split(u->lc, pos);
u = new (_curr++) Node(u->val, res.second, u->rc);
} else {
res = split(u->rc, pos - size(u->lc) - 1);
u = new (_curr++) Node(u->val, u->lc, res.first);
}

return res;
}
};

int main() {

return 0;
}

并查集

LibreOJ 对应模版题代码。

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
/*
* Algorithm template : Union Find Set
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>

const int MAXN = 4000005;
const int MOD = 998244353;

struct UnionFindSet {
int fa[MAXN];

void init(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(y)] = find(x);
}

int test(int x, int y) {
return find(x) == find(y) ? 1 : 0;
}
} ufs;

int main() {
int n, q;
scanf("%d %d", &n, &q);

ufs.init(n);

int ans = 0;
while (q--) {
int op, u, v;
scanf("%d %d %d", &op, &u, &v);
if (op == 0) {
ufs.merge(u, v);
} else {
ans = ans << 1 | ufs.test(u, v);
ans >= MOD ? ans -= MOD : 0;
}
}

printf("%d\n", ans);

return 0;
}

稀疏表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
* Algorithm template : Range Minimum Query - Sparse Table
*
* by: Pepcy_Ch
* time: 2017.7.17
*/

#include <cstdio>
#include <algorithm>

const int MAXN = 500005;
const int MAXN_LOG = 20;

struct SparseTable {
int st[MAXN][MAXN_LOG], log[MAXN];

void init(int *a, int n) {
int t = 0;
for (int i = 0; i <= n; i++) {
while (1 << (t + 1) <= i) t++;
log[i] = t;
}

for (int i = 1; i <= n; i++) st[i][0] = a[i];

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= log[n]; j++) {
if (i + (1 << j) <= n) st[i][j] = std::min(st[i][j - 1], st[i + (1 << j)][j - 1]);
else st[i][j] = st[i][j - 1];
}
}
}

int query(int l, int r) {
int t = log[r - l];
return std::min(st[l][t], st[r - (1 << t) + 1][t]);
}
} st;

int main() {
int n;
scanf("%d", &n);

static int a[MAXN];
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

st.init(a, n);

int q;
scanf("%d", &q);
while (q--) {
int l, r;
scanf("%d %d", &l, &r);
printf("%d\n", st.query(l, r));
}
return 0;
}

图与树

单源最短路

Dijkstra。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
/*
* Algotirhm template : Single Source Shortest Path - Dijkstra
*
* by: Pepcy_Ch
* time: 2017.7.10
*/

#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>

const int MAXN = 100005;
const int MAXM = 500005;

struct Edge;
struct Node;

struct Node {
Edge *e; // use std::vector<Edge> when dense graph.
int dist;
bool vis;
} N[MAXN];

struct Edge {
Node *u, *v;
Edge *next;
int w;

Edge() {}
Edge(Node *u, Node *v, int w) : u(u), v(v), w(w), next(u->e) {}
} _pool[MAXM << 1], *_curr = _pool;
void addEdge(int u, int v, int w) {
N[u].e = new (_curr++) Edge(&N[u], &N[v], w);
N[v].e = new (_curr++) Edge(&N[v], &N[u], w);
}

namespace Dijkstra {
typedef std::pair<int, Node *> HeapNode;

void dijkstra(Node *s) {
std::priority_queue<HeapNode, std::vector<HeapNode>, std::greater<HeapNode> > q;
s->dist = 0;
q.push(std::make_pair(0, s));

while (!q.empty()) {
Node *u = q.top().second;
q.pop();

if (u->vis) continue;
u->vis = true;

for (Edge *e = u->e; e; e = e->next) {
if (e->v->dist > u->dist + e->w) {
e->v->dist = u->dist + e->w;

q.push(std::make_pair(e->v->dist, e->v));
}
}
}
}

int solve(int s, int t, int n) {
for (int i = 1; i <= n; i++) {
N[i].dist = INT_MAX;
N[i].vis = false;
}

dijkstra(&N[s]);

return N[t].dist;
}
}

int main() {
int n, m, s, t;
scanf("%d %d %d %d", &n, &m, &s, &t);

for (int i = 0, u, v, w; i < m; i++) {
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
}

printf("%d\n", Dijkstra::solve(s, t, n));

return 0;
}

分层最短路,为 JLOI 2011 飞行路线的代码。

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
/*
* Algorithm template : Layered Single Source Shortest Path - Dijkstra
*
* by: Pepcy_Ch
* time: 2017.7.10
*/

#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>

const int MAXN = 10005;
const int MAXM = 50005;
const int MAXK = 10;

struct Edge;
struct Node;

struct Node {
Edge *e; // use std::vector<Edeg> when dense graph
int dist[MAXK];
bool vis[MAXK];
} N[MAXN];

struct Edge {
Node *u, *v;
Edge *next;
int w;

Edge() {}
Edge(Node *u, Node *v, int w) : u(u), v(v), w(w), next(u->e) {}
} _pool[MAXM << 1], *_curr = _pool;
void addEdge(int u, int v, int w) {
N[u].e = new (_curr++) Edge(&N[u], &N[v], w);
N[v].e = new (_curr++) Edge(&N[v], &N[u], w);
}

namespace Dijkstra {
struct HeapNode {
Node *u;
int dist, k;

HeapNode(Node *u, int k, int dist) : u(u), k(k), dist(dist) {}

bool operator<(const HeapNode &rhs) const {
return dist > rhs.dist;
}
};

void dijkstra(Node *s, int maxK) {
std::priority_queue<HeapNode> q;
s->dist[0] = 0;
q.push(HeapNode(s, 0, 0));

while (!q.empty()) {
Node *u = q.top().u;
int k = q.top().k;
q.pop();

if (u->vis[k]) continue;
u->vis[k] = true;

for (Edge *e = u->e; e; e = e->next) {
if (e->v->dist[k] > u->dist[k] + e->w) {
e->v->dist[k] = u->dist[k] + e->w;

q.push(HeapNode(e->v, k, e->v->dist[k]));
}

if (k < maxK && e->v->dist[k + 1] > u->dist[k]) {
e->v->dist[k + 1] = u->dist[k];

q.push(HeapNode(e->v, k + 1, e->v->dist[k + 1]));
}
}
}
}

int solve(int s, int t, int n, int k) {
for (int i = 1; i <= n; i++) {
std::fill(N[i].dist, N[i].dist + k + 1, INT_MAX);
std::fill(N[i].vis, N[i].vis + k + 1, false);
}

dijkstra(&N[s], k);

int res = INT_MAX;
for (int i = 0; i <= k; i++) res = std::min(res, N[t].dist[i]);
return res;
}
}
int main() {
int n, m, k, s, t;
scanf("%d %d %d %d %d", &n, &m, &k, &s, &t);

for (int i = 0, u, v, w; i < m; i++) {
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
}

printf("%d\n", Dijkstra::solve(s, t, n, k));
return 0;
}

队列优化的 Bellman-Ford(用于差分约束)。

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
/*
* Algorithm template : Single Source Shortest Path with negative value : queue-optimized Bellman-Ford
*
* by: Pepcy_Ch
* time: 2017.7.10
*/

#include <cstdio>
#include <climits>
#include <queue>
#include <algorithm>

const int MAXN = 100005;
const int MAXM = 500005;

struct Edge;
struct Node;

struct Node {
Edge *e; // use std::vetor<Edge> when dense graph
int dist, cnt;
bool inq;
} N[MAXN];

struct Edge {
Node *u, *v;
Edge *next;
int w;

Edge() {}
Edge(Node *u, Node *v, int w) : u(u), v(v), w(w), next(u->e) {}
} _pool[MAXM << 1], *_curr = _pool;
void addEdge(int u, int v, int w) {
N[u].e = new (_curr++) Edge(&N[u], &N[v], w);
N[v].e = new (_curr++) Edge(&N[v], &N[u], w);
}

namespace BellmanFord {
bool bellmanFord(Node *s, int n) {
std::queue<Node *> q;
q.push(s);
s->dist = 0;

while (!q.empty()) {
Node *u = q.front();
q.pop();
u->inq = false;

for (Edge *e = u->e; e; e = e->next) {
if (e->v->dist > u->dist + e->w) {
e->v->dist = u->dist + e->w;

if (++e->v->cnt >= n) return false;
if (!e->v->inq) {
e->v->inq = true;
q.push(e->v);
}
}
}
}
return true;
}
int solve(int s, int t, int n) {
for (int i = 1; i <= n; i++) {
N[i].dist = INT_MAX;
N[i].cnt = 0;
N[i].inq = false;
}

return bellmanFord(&N[s], n) ? N[t].dist : -1;
}
}

int main() {
int n, m, s, t;
scanf("%d %d %d %d", &n, &m, &s, &t);

for (int i = 0, u, v, w; i < m; i++) {
scanf("%d %d %d", &u ,&v, &w);
addEdge(u, v, w);
}

printf("%d\n", BellmanFord::solve(s, t, n));

return 0;
}

Floyd

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
/*
* Algorithm template : Floyd
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>
#include <climits>
#include <algorithm>

const int MAXN = 1005;

int dist[MAXN][MAXN];

void floyd(int n) {
for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) if (dist[i][k] < INT_MAX) {
for (int j = 1; j <= n; j++) if (dist[k][j] < INT_MAX)
dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
}
}

int main() {
int n, m;
scanf("%d %d", &n, &m);

std::fill((int *) dist, (int *) dist + MAXN * MAXN, INT_MAX);

for (int i = 0, u, v, w; i < m; i++) {
scanf("%d %d %d", &u, &v, &w);
dist[u][v] = dist[v][u] = w;
}

/*
* dist[i][i] = 0 : calc shortest path from u to v
* dist[i][i] = INT_MAX : calc shortest circle
* dist[i][i] > 0 : calc how many shortest paths from u to v through i
*/

floyd(n);

return 0;
}

bitset 优化的 Floyd(可稍加修改为 JSOI 2010 连通数代码)。

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
/*
* Algorithm template : Connectivity Judge - Bitset-optimized Floyd
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>
#include <bitset>
#include <algorithm>

const int MAXN = 2005;

std::bitset<MAXN> G[MAXN];

void floyd(int n) {
for (int k = 0; k < n; k++) for (int i = 0; i < n; i++)
if (G[i][k]) G[i] |= G[k];
}

int main() {
int n, m;
scanf("%d %d", &n, &m);

for (int i = 0, u, v; i < m; i++) {
scanf("%d %d", &u, &v);
G[u][v] = 1;
}
for (int i = 0; i < n; i++) G[i][i] = 1;

floyd(n);

return 0;
}

网络流

LibreOJ 对应模版题代码。

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
/*
* Algorithm template : Network Flow : Dinic
*
* by: Pepcy_Ch
* time: 2017.7.11
*/

#include <cstdio>
#include <climits>
#include <queue>
#include <vector>
#include <algorithm>

const int MAXN = 1000005;
const int MAXM = 4000005;

struct Edge;
struct Node;

struct Node {
std::vector<Edge> e; // use Edge* when sparse graph
Edge *curr;
int level;
} N[MAXN];

struct Edge {
Node *u,*v;
int cap, flow, rev;

Edge(Node *u, Node *v, int cap, int rev) : u(u), v(v), cap(cap), flow(0), rev(rev) {}
};
void addEdge(int u, int v, int cap) {
N[u].e.push_back(Edge(&N[u], &N[v], cap, N[v].e.size()));
N[v].e.push_back(Edge(&N[v], &N[u], 0, N[u].e.size() - 1));
}

namespace Dinic {
bool level(Node *s, Node *t, int n) {
for (int i = 0; i < n; i++) N[i].level = 0;

std::queue<Node *> q;
q.push(s);
s->level = 1;

while (!q.empty()) {
Node *u = q.front();
q.pop();

for (Edge *e = &u->e.front(); e <= &u->e.back(); e++) {
if (e->cap > e->flow && e->v->level == 0) {
e->v->level = u->level + 1;
if (e->v == t) return true;
q.push(e->v);
}
}
}

return false;
}

int findPath(Node *u, Node *t, int limit = INT_MAX) {
if (u == t) return limit;

for (Edge *&e = u->curr; e <= &u->e.back(); e++) {
if (e->cap > e->flow && e->v->level == u->level + 1) {
int flow = findPath(e->v, t, std::min(limit, e->cap - e->flow));
if (flow > 0) {
e->flow += flow;
e->v->e[e->rev].flow -= flow;
return flow;
}
}
}

return 0;
}

int solve(int s, int t, int n) {
int res = 0;

while (level(&N[s], &N[t], n)) {
for (int i = 0; i < n; i++) N[i].curr = &N[i].e.front();
int flow;
while ((flow = findPath(&N[s], &N[t], n)) > 0) res += flow;
}

return res;
}
}

int main() {
int n, m, s, t;
scanf("%d %d %d %d", &n, &m, &s, &t);

for (int i = 0, u, v, w; i < m; i++) {
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w);
}

printf("%d\n", Dinic::solve(s, t, n));

return 0;
}

费用流

LibreOJ 对应模版题代码

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
/*
* Algorithm template : Max Flow Min Cost : Edmonds-Karp
*
* by: Pepcy_Ch
* time: 2017.7.11
*/

#include <cstdio>
#include <climits>
#include <queue>
#include <vector>
#include <algorithm>

const int MAXN = 405;
const int MAXM = 15005;

struct Edge;
struct Node;

struct Node {
std::vector<Edge> e; // use Edge* when sparse graph
Edge *pre;
int dist, flow;
bool inq;
} N[MAXN];

struct Edge {
Node *u, *v;
int cap, flow, cost, rev;

Edge(Node *u, Node *v, int cap, int cost, int rev) : u(u), v(v), cap(cap), flow(0), cost(cost), rev(rev) {}
};
void addEdge(int u, int v, int cap, int cost) {
N[u].e.push_back(Edge(&N[u], &N[v], cap, cost, N[v].e.size()));
N[v].e.push_back(Edge(&N[v], &N[u], 0, -cost, N[v].e.size() - 1));
}

namespace EdmondsKarp {
void solve(int s, int t, int n, int &flow, int &cost) {
flow = cost = 0;

while (true) {
for (int i = 0; i < n; i++) {
N[i].pre = NULL;
N[i].inq = false;
N[i].dist = INT_MAX;
N[i].flow = 0;
}

std::queue<Node *> q;
q.push(&N[s]);
N[s].dist = 0;
N[s].flow = INT_MAX;

while (!q.empty()) {
Node *u = q.front();
q.pop();
u->inq = false;

for (Edge *e = &u->e.front(); e <= &u->e.back(); e++) {
if (e->cap > e->flow && e->v->dist > u->dist + e->cost) {
e->v->dist = u->dist + e->cost;
e->v->flow = std::min(u->flow, e->cap - e->flow);
e->v->pre = e;

if (!e->v->inq) {
e->v->inq = true;
q.push(e->v);
}
}
}
}
if (N[t].dist == INT_MAX) break;

for (Edge *e = N[t].pre; e; e = e->u->pre) {
e->flow += N[t].flow;
e->v->e[e->rev].flow -= N[t].flow;
}

flow += N[t].flow;
cost += N[t].flow * N[t].dist;
}
}
}

int main() {
int n, m, s, t;
scanf("%d %d %d %d", &n, &m, &s, &t);

for (int i = 0, u, v, w, c; i < m; i++) {
scanf("%d %d %d %d", &u, &v, &w, &c);
addEdge(u, v, w, c);
}

int flow, cost;
EdmondsKarp::solve(s, t, n, flow, cost);
printf("%d\n", flow);

return 0;
}

无源无汇上下界可行流

LibreOJ 对应模版题代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/*
* Algorithm template : Accepted Flow with Lower and Upper Bound and wothout Source and Convergence
*
* by: Pepcy_Ch
* time: 2017.7.11;
*/

#include <cstdio>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>

const int MAXN = 205;
const int MAXM = 10205;

struct Edge;
struct Node;

struct Node {
std::vector<Edge> e;
Edge *curr;
int level, extra;
} N[MAXN];

struct Edge {
Node *u, *v;
int cap, flow, rev;

Edge(Node *u, Node *v, int cap, int rev) : u(u), v(v), cap(cap), flow(0), rev(rev) {}
};

struct Pair {
int u, num, lower;

Pair() {}
Pair(int u, int num, int lower) : u(u), num(num), lower(lower) {}

int flow() const {
return N[u].e[num].flow + lower;
}
} E[MAXM];

Pair addEdge(int u, int v, int lower, int upper) {
int cap = upper - lower;
N[u].e.push_back(Edge(&N[u], &N[v], cap, N[v].e.size()));
N[v].e.push_back(Edge(&N[v], &N[u], 0, N[u].e.size() - 1));

N[u].extra -= lower;
N[v].extra += lower;

return Pair(u, N[u].e.size() - 1, lower);
}

namespace Dinic {
bool level(Node *s, Node *t, int n) {
for (int i = 0; i < n; i++) N[i].level = 0;

std::queue<Node *> q;
q.push(s);
s->level = 1;

while (!q.empty()) {
Node *u = q.front();
q.pop();

for (Edge *e = &u->e.front(); e <= &u->e.back(); e++) {
if (e->cap > e->flow && e->v->level == 0) {
e->v->level = u->level + 1;
if (e->v == t) return true;
q.push(e->v);
}
}
}

return false;
}

int findPath(Node *u, Node *t, int limit = INT_MAX) {
if (u == t) return limit;

for (Edge *&e = u->curr; e <= &u->e.back(); e++) {
if (e->cap > e->flow && e->v->level == u->level + 1) {
int flow = findPath(e->v, t, std::min(limit, e->cap - e->flow));
if (flow > 0) {
e->flow += flow;
e->v->e[e->rev].flow -= flow;
return flow;
}
}
}

return 0;
}

int solve(int s, int t, int n) {
int res = 0;

while (level(&N[s], &N[t], n)) {
for (int i = 0; i < n; i++) N[i].curr = &N[i].e.front();
int flow;
while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
}

return res;
}
}

int main() {
int n, m;
scanf("%d %d", &n, &m);
const int s = 0, t = n + 1;

for (int i = 0, u, v, lower, upper; i < m; i++) {
scanf("%d %d %d %d", &u, &v, &lower, &upper);
E[i] = addEdge(u, v, lower, upper);
}

int sum = 0;
for (int i = 1; i <= n; i++) {
if (N[i].extra > 0) {
sum += N[i].extra;
addEdge(s, i, 0, N[i].extra);
} else if (N[i].extra < 0) {
addEdge(i, t, 0, -N[i].extra);
}
}

int maxFlow = Dinic::solve(s, t, n + 2);
if (maxFlow < sum) {
puts("NO");
} else {
puts("YES");
for (int i = 0; i < m; i++) printf("%d\n", E[i].flow());
}
return 0;
}

有源有汇上下界最大流

LibreOJ 对应模版题代码。

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
/*
* Algorithm template : Max Flow with Lower ans Upper Bound
*
* by: Pepcy_Ch
* time: 2017.7.11
*/

#include <cstdio>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>

const int MAXN = 205;
const int MAXM = 10000;

struct Edge;
struct Node;

struct Node {
std::vector<Edge> e;
Edge *curr;
int level, extra;
} N[MAXN];

struct Edge {
Node *u, *v;
int cap, flow, rev;

Edge(Node *u, Node *v, int cap, int rev) : u(u), v(v), cap(cap), flow(0), rev(rev) {}
};
void addEdge(int u, int v, int lower, int upper) {
int cap = upper - lower;
N[u].e.push_back(Edge(&N[u], &N[v], cap, N[v].e.size()));
N[v].e.push_back(Edge(&N[v], &N[u], 0, N[u].e.size() - 1));

N[u].extra -= lower;
N[v].extra += lower;
}

namespace Dinic {
bool level(Node *s, Node *t, int n) {
for (int i = 0; i < n; i++) N[i].level = 0;

std::queue<Node *> q;
q.push(s);
s->level = 1;

while (!q.empty()) {
Node *u = q.front();
q.pop();

for (Edge *e = &u->e.front(); e <= &u->e.back(); e++) {
if (e->cap > e->flow && e->v->level == 0) {
e->v->level = u->level + 1;
if (e->v == t) return true;
q.push(e->v);
}
}
}

return false;
}

int findPath(Node *u, Node *t, int limit = INT_MAX) {
if (u == t) return limit;

for (Edge *&e = u->curr; e <= &u->e.back(); e++) {
if (e->cap > e->flow && e->v->level == u->level + 1) {
int flow = findPath(e->v, t, std::min(limit, e->cap - e->flow));
if (flow > 0) {
e->flow += flow;
e->v->e[e->rev].flow -= flow;
return flow;
}
}
}

return 0;
}

int solve(int s, int t, int n) {
int res = 0;

while (level(&N[s], &N[t], n)) {
for (int i = 0; i < n; i++) N[i].curr = &N[i].e.front();
int flow;
while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
}

return res;
}
}

int main() {
int n, m, s, t;
scanf("%d %d %d %d", &n, &m, &s, &t);
const int S = 0, T = n + 1;

for (int i = 0, u, v, lower, upper; i < m; i++) {
scanf("%d %d %d %d", &u, &v, &lower, &upper);
addEdge(u, v, lower, upper);
}
addEdge(t, s, 0, INT_MAX);
int sum = 0;
for (int i = 1; i <= n; i++) {
if (N[i].extra > 0) {
sum += N[i].extra;
addEdge(S, i, 0, N[i].extra);
} else if (N[i].extra < 0) {
addEdge(i, T, 0, -N[i].extra);
}
}

int maxFlow = Dinic::solve(S, T, n + 2);
if (maxFlow < sum) {
puts("please go home to sleep");
} else {
printf("%d\n", Dinic::solve(s, t, n + 2));
}
return 0;
}

有源有汇上下界最小流

LibreOJ 对应模版题代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
/*
* Algorithm template : Min Flow with Lower and Upper Bound
*
* by: Pepcy_Ch
* time: 2017.7.11
*/

#include <cstdio>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>

const int MAXN = 50005;
const int MAXM = 125005;

struct Edge;
struct Node;

struct Node {
Edge *e, *curr;
int level, extra;
} N[MAXN];

struct Edge {
Node *u, *v;
Edge *next, *rev;
int cap, flow;

Edge() {}
Edge(Node *u, Node *v, int cap) : u(u), v(v), cap(cap), flow(0), next(u->e) {}
} _pool[MAXM + MAXN << 1], *_curr = _pool;
Edge *addEdge(int u, int v, int lower, int upper) {
int cap = upper - lower;
N[u].e = new (_curr++) Edge(&N[u], &N[v], cap);
N[v].e = new (_curr++) Edge(&N[v], &N[u], 0);
(N[u].e->rev = N[v].e)->rev = N[u].e;

N[u].extra -= lower;
N[v].extra += lower;

return N[u].e;
}

namespace Dinic {
bool level(Node *s, Node *t, int n) {
for (int i = 0; i < n; i++) N[i].level = 0;

std::queue<Node *> q;
q.push(s);
s->level = 1;

while (!q.empty()) {
Node *u = q.front();
q.pop();

for (Edge *e = u->e; e; e = e->next) {
if (e->cap > e->flow && e->v->level == 0) {
e->v->level = u->level + 1;
if (e->v == t) return true;
q.push(e->v);
}
}
}

return false;
}

int findPath(Node *u, Node *t, int limit = INT_MAX) {
if (u == t) return limit;

for (Edge *&e = u->curr; e; e = e->next) {
if (e->cap > e->flow && e->v->level == u->level + 1) {
int flow = findPath(e->v, t, std::min(limit, e->cap - e->flow));
if (flow > 0) {
e->flow += flow;
e->rev->flow -= flow;
return flow;
}
}
}

return 0;
}

int solve(int s, int t, int n) {
int res = 0;

while (level(&N[s], &N[t], n)) {
for (int i = 0; i < n; i++) N[i].curr = N[i].e;
int flow;
while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
}

return res;
}
}

int main() {
int n, m, s, t;
scanf("%d %d %d %d", &n, &m, &s, &t);
const int S = 0, T = n + 1;

for (int i = 0, u, v, lower, upper; i < m; i++) {
scanf("%d %d %d %d", &u, &v, &lower, &upper);
addEdge(u, v, lower, upper);
}
Edge *e = addEdge(t, s, 0, INT_MAX);
int sum = 0;
for (int i = 1; i <= n; i++) {
if (N[i].extra > 0) {
sum += N[i].extra;
addEdge(S, i, 0, N[i].extra);
} else if (N[i].extra < 0) {
addEdge(i, T, 0, -N[i].extra);
}
}

int maxFlow = Dinic::solve(S, T, n + 2);
if (maxFlow < sum) {
puts("please go home to sleep");
} else {
int flow = e->flow;
e->cap = e->rev->cap = 0;
printf("%d\n", flow - Dinic::solve(t, s, n + 2));
}
return 0;
}

Tarjan

找强连通分量并缩点建图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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
/*
* Algorithm template : Strongly Connected Componenet : Tarjan
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>
#include <stack>
#include <algorithm>

const int MAXN = 100005;
const int MAXM = 500005;

template <typename T>
struct Edge {
T *u, *v;
Edge *next;

Edge() {}
Edge(T *u, T *v) : u(u), v(v), next(u->e) {}
};

struct Comp {
Edge<Comp> *e;
int size;
} C[MAXN];
Edge<Comp> _poolC[MAXM], *_currC = _poolC;
void addEdge(Comp *u, Comp *v) {
u->e = new (_currC++) Edge<Comp>(u, v);
}

struct Node {
Edge<Node> *e;
Comp *c;
int dfn, low;
bool ins;
} N[MAXN];
Edge<Node> _poolN[MAXM], *_currN = _poolN;
void addEdge(int u, int v) {
N[u].e = new (_currN++) Edge<Node>(&N[u], &N[v]);
}

namespace Tarjan {
int dfsClock, compCnt;
std::stack<Node *> s;

void dfs(Node *u) {
u->dfn = u->low = ++dfsClock;
s.push(u);
u->ins = true;

for (Edge<Node> *e = u->e; e; e = e->next) {
if (!e->v->dfn) {
dfs(e->v);
u->low = std::min(u->low, e->v->low);
} else if (e->v->ins) {
u->low = std::min(u->low, e->v->dfn);
}
}

if (u->dfn == u->low) {
Comp *c = &C[++compCnt];
Node *v;

do {
v = s.top();
s.pop();
v->ins = false;
v->c = c;
c->size++;
} while (u != v);
}
}

void findSCC(int n) {
dfsClock = compCnt = 0;
while (!s.empty()) s.pop();

for (int i = 1; i <= n; i++) if (!N[i].dfn) dfs(&N[i]);
}
}

void rebuild() {
for (Edge<Node> *e = _poolN; e != _currN; e++)
if (e->u->c != e->v->c) addEdge(e->u->c, e->v->c);
}

int main() {
int n, m;
scanf("%d %d", &n, &m);

for (int i = 0, u, v; i < m; i++) {
scanf("%d %d", &u, &v);
addEdge(u, v);
}

Tarjan::findSCC(n);

rebuild();

return 0;
}

虚树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
/*
* Algorithm template : Virtual Tree
*
* by: Pepcy_Ch
* time: 2017.7.15
*/

#include <cstdio>
#include <algorithm>

const int MAXN = 300005;
const int MAXN_LOG = 20;

template <typename T>
struct Edge {
T *u, *v;
Edge *next;

Edge() {}
Edge(T *u, T *v) : u(u), v(v), next(u->e) {}
};

struct Node {
Edge<Node> *e;
Node *f[MAXN_LOG];
int dfn, dep;
} N[MAXN];
Edge<Node> _poolN[MAXN << 1], *_currN = _poolN;
void addEdge(int u, int v) {
N[u].e = new (_currN++) Edge<Node>(&N[u], &N[v]);
N[v].e = new (_currN++) Edge<Node>(&N[v], &N[u]);
}

struct VirN {
Edge<VirN> *e;
Node *r;
} V[MAXN];
Edge<VirN> _poolV[MAXN << 1], *_currV = _poolV;
void addEdge(VirN *u, VirN *v) {
u->e = new (_currV++) Edge<VirN>(u, v);
v->e = new (_currV++) Edge<VirN>(v, u);
}

void dfs(Node *u, bool init = true) {
if (init) {
u->dep = 1;
u->f[0] = u;
}

static int dfsClock = 0;
u->dfn = ++dfsClock;

for (int i = 1; i < MAXN_LOG; i++) u->f[i] = u->f[i - 1]->f[i - 1];

for (Edge<Node> *e = u->e; e; e = e->next) if (e->v != u->f[0]) {
e->v->f[0] = u;
e->v->dep = u->dep + 1;
dfs(e->v, false);
}
}

Node *lca(Node *u, Node *v) {
if (u->dep < v->dep) std::swap(u, v);

for (int i = MAXN_LOG - 1; ~i; i--) {
if (u->f[i]->dep >= v->dep) u = u->f[i];
}

for (int i = MAXN_LOG - 1; ~i; i--) {
if (u->f[i] != v->f[i]) {
u = u->f[i];
v = v->f[i];
}
}

return u == v ? u : u->f[0];
}

void build(bool flag, int n, int &tot) {
static VirN *stack[MAXN];
int top = 0;

if (!flag) stack[top++] = &V[0];

for (int i = 1; i <= n; i++) {
if (!top) {
stack[top++] = &V[i];
continue;
}
Node *p = lca(stack[top - 1]->r, V[i].r);
if (p == stack[i - 1]->r) {
stack[top++] = &V[i];
continue;
}
while (top - 2 >= 0 && stack[top - 2]->r->dep >= p->dep) {
addEdge(stack[top - 2], stack[top - 1]);
top--;
}
if (stack[top - 1]->r != p) {
V[++tot].r = p;
addEdge(&V[tot], stack[--top]);
stack[top++] = &V[tot];
}
stack[top++] = &V[i];
}

for (int i = 0; i < top - 1; i++) addEdge(stack[i], stack[i + 1]);
}

bool cmp(int i, int j) {
return N[i].dfn < N[j].dfn;
}

void clear(int n) {
_currV = _poolV;
for (int i = 0; i <= n; i++) V[i].e = NULL;
}

void solve() {
int k;
scanf("%d", &k);
clear(k);

static int order[MAXN], h[MAXN];
for (int i = 0; i < k; i++) scanf("%d", &h[i]), order[i] = h[i];

std::sort(h, h + k, cmp);
int tot = 0;
bool flag = h[0] == 1;
for (int i = 0; i < k; i++) V[++tot].r = &N[h[i]];
build(flag, tot, tot);
}

int main() {
int n;
scanf("%d", &n);

for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
addEdge(u, v);
}

dfs(&N[1]);

V[0].r = &N[1];
int q;
scanf("%d", &q);
while (q--) solve();

return 0;
}

字符串

后缀数组

UOJ 对应模版题代码。

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
/*
* Algorithm template : Suffix Array
*
* by: Pepcy_Ch
* time: 2017.7,14
*/

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 1000005;

namespace SuffixArray {
int n, sa[MAXN], rank[MAXN], height[MAXN];
char str[MAXN];

void buildSA(int m) {
static int fir[MAXN], sec[MAXN], buc[MAXN], temp[MAXN];
n = strlen(str);
str[n++] = 0;

std::fill(buc, buc + m, 0);
for (int i = 0; i < n; i++) buc[(int) str[i]]++;
for (int i = 1; i < m; i++) buc[i] += buc[i - 1];
for (int i = 0; i < n; i++) rank[i] = buc[(int) str[i]] - 1;

for (int l = 1; l < n; l <<= 1) {
for (int i = 0; i < n; i++)
fir[i] = rank[i], sec[i] = i + l < n ? rank[i + l] : 0;

std::fill(buc, buc + n, 0);
for (int i = 0; i < n; i++) buc[sec[i]]++;
for (int i = 1; i < n; i++) buc[i] += buc[i - 1];
for (int i = n - 1; ~i; i--) temp[--buc[sec[i]]] = i;

std::fill(buc, buc + n, 0);
for (int i = 0; i < n; i++) buc[fir[i]]++;
for (int i = 1; i < n; i++) buc[i] += buc[i - 1];
for (int i = n - 1; ~i; i--) sa[--buc[fir[temp[i]]]] = temp[i];

rank[sa[0]] = 0;
bool unique = true;
for (int i = 1; i < n; i++) {
rank[sa[i]] = rank[sa[i - 1]];
if (fir[sa[i]] == fir[sa[i - 1]] && sec[sa[i]] == sec[sa[i - 1]]) unique = false;
else rank[sa[i]]++;
}

if (unique) break;
}
}

void getHeight() {
int k = 0;
for (int i = 0; i < n - 1; i++) {
k ? k-- : 0;
int j = sa[rank[i] - 1];
while (str[i + k] == str[j + k]) k++;
height[rank[i]] = k;
}
}
}

int main() {
char *str = SuffixArray::str;
scanf("%s", str);

SuffixArray::buildSA(128);
int *sa = SuffixArray::sa, n = SuffixArray::n;
for (int i = 1; i < n; i++) printf("%d%c", sa[i] + 1, " \n"[i == n - 1]);

SuffixArray::getHeight();
int *height = SuffixArray::height + 1;
for (int i = 1; i < n - 1; i++) printf("%d%c", height[i], " \n"[i == n - 2]);

return 0;
}

后缀自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/*
* Algorithm template : Suffix Automaton
*
* by: Pepcy_Ch
* time: 2017.7.14
*/

#include <cstdio>
#include <vector>
#include <algorithm>

const int MAXN = 100005;
const int CHAR_SET = 'z' - 'a' + 1;
const char BASE_CHAR = 'a';

struct SAM {
struct Node {
Node *c[CHAR_SET], *next;
int max, posCnt;

Node(int max = 0, bool newSuffix = false) : max(max), posCnt(newSuffix), next(NULL), c() {}

int min() const {
return next->max + 1;
}
} *start, *last, _pool[MAXN << 1], *_curr;

SAM() {
init();
}

void init() {
_curr = _pool;
start = last = new (_curr++) Node;
}

Node *extend(int c) {
Node *u = new (_curr++) Node(last->max + 1, true), *v = last;

for (; v && !v->c[c]; v = v->next) v->c[c] = u;

if (!v) {
u->next = start;
} else if (v->c[c]->max == v->max + 1) {
u->next = v->c[c];
} else {
Node *n = new (_curr++) Node(v->max + 1), *o = v->c[c];
std::copy(o->c, o->c + CHAR_SET, n->c);
n->next = o->next;
u->next = o->next = n;
for (; v && v->c[c] == o; v = v->next) v->c[c] = n;
}

return last = u;
}

std::vector<Node *> topo;
std::vector<Node *> toposort() {
static int buc[MAXN << 1];
int max = 0;
for (Node *p = _pool; p != _curr; p++) {
max = std::max(max, p->max);
buc[p->max]++;
}
for (int i = 1; i <= max; i++) buc[i] += buc[i - 1];

topo.resize(_curr - _pool);
for (Node *p = _pool; p != _curr; p++) topo[--buc[p->max]] = p;

return topo;
}

void calc() {
toposort();

for (int i = 0; i < topo.size(); i++) topo[i]->next->posCnt += topo[i]->posCnt;
}
} sam;

int main() {

return 0;
}

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
/*
* Algorithm template : Aho-Corasick Automaton
*
* by: Pepcy_Ch
* time: 2017.7.13
*/

#include <cstdio>
#include <queue>
#include <algorithm>

const int MAXN = 100005;
const int CHAR_SET = 'z' - 'a' + 1;
const char BASE_CHAR = 'a';

struct ACAM {
struct Node {
Node *c[CHAR_SET], *next, *fail;
bool isWord;
int refCnt;

Node(bool isWord = false)
: c(), next(NULL), fail(NULL), isWord(isWord), refCnt(0) {}

void apply() {
refCnt++;
if (next) next->apply();
}
} *root;

ACAM() : root(new Node) {}

Node *insert(char *begin, char *end) {
Node **u = &root;
for (char *p = begin; p != end; p++) {
if (!(*u)) *u = new Node;
u = &(*u)->c[*p - BASE_CHAR];
}

if (!(*u)) *u = new Node(true);
else (*u)->isWord = true;

return *u;
}

void build() {
std::queue<Node *> q;
q.push(root);
root->fail = root;
root->next = NULL;

while (!q.empty()) {
Node *u = q.front();
q.pop();

for (int i = 0; i < CHAR_SET; i++) {
Node *&c = u->c[i];

if (!c) {
c = u == root ? root : u->fail->c[i];
continue;
}

Node *v = u->fail;
c->fail = u != root && v->c[i] ? v->c[i] : root;
c->next = c->fail->isWord ? c->fail : c->fail->next;
q.push(c);
}
}
}

void exec(char *begin, char *end) {
Node *u = root;
for (char *p = begin; p != end; p++) {
u = u->c[*p - CHAR_SET];
if (u->isWord) u->apply();
else if (u->next) u->next->apply();
}
}
} acam;

int main() {

return 0;
}

Manacher

稍加修改为 POJ 3974 代码。

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
/*
* Algorithm template : Manacher
*
* by: Pepcy_Ch
* time: 2017.7.14
*/

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 1000005;

namespace Manacher {
char s[MAXN << 1];
int r[MAXN << 1], len;

void prepare(char *str) {
len = 0;
s[++len] = '@';
s[++len] = '#';
int n = strlen(str);
for (int i = 0; i < n; i++) s[++len] = str[i], s[++len] = '#';
s[++len] = '\0';
}

void manacher() {
int right = 0, pos = 0;
for (int i = 1; i <= len; i++) {
int x = right < i ? 1 : std::min(r[2 * pos - i], right - i);
while (s[i + x] == s[i - x]) x++;
r[i] = x;
if (x + i > right) {
right = x + i;
pos = i;
}
}
}

void calc(char *str) {
prepare(str);
manacher();
}
}

int main() {
static char s[MAXN];
scanf("%s", s);

Manacher::calc(s);

int ans = 0, len = Manacher::len, *r = Manacher::r;
for (int i = 1; i <= len; i++) ans = std::max(ans, r[i] - 1);

printf("%d\n", ans);

return 0;
}

回文树

APIO 2014 Palindrome 代码。

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
/*
* Algorithm template : Palindrome Tree
*
* by: Pepcy_Ch
* time: 2017.7.15
*/

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 300005;
const int CHAR_SET = 'z' - 'a' + 1;
const char BASE_CHAR = 'a';

struct PalinT {
struct Node {
Node *c[CHAR_SET], *fail;
int len, cnt;

Node(int len = 0) : len(len), cnt(0), c(), fail(NULL) {}
} *even, *odd, *last, _pool[MAXN], *_curr;
char str[MAXN];
int size;

PalinT() : str() {
_curr = _pool;
last = even = new (_curr++) Node;
even->fail = odd = new (_curr++) Node(-1);
odd->fail = odd;
str[size = 0] = -1;
}

Node *extend(int c) {
str[++size] = c;
for (; str[size - last->len - 1] != str[size]; last = last->fail) {}

Node *v = last, *u = v->c[c];
if (!u) {
u = new (_curr++) Node(v->len + 2);
Node *p = v->fail;
for (last = last->fail; str[size - last->len - 1] != str[size]; last = last->fail) {}
u->fail = last == odd && !odd->c[c] ? even : last->c[c];
v->c[c] = u
}
u->cnt++;

return last = u;
}

void build(char *begin, char *end) {
for (char *p = begin; p != end; p++) extend(*p - BASE_CHAR);
}

void count() {
for (Node *p = _curr - 1; p >= _pool; p--) p->fail->cnt += p->cnt;
}
} palinT;

int main() {
static char s[MAXN];
scanf("%s", s);

int n = strlen(s);
palinT.build(s, s + n);
palinT.count();

long long ans = 0;
for (PalinT::Node *p = palinT._pool; p != palinT._curr; p++)
ans = std::max(ans, (long long) p->len * p->cnt);

printf("%lld\n", ans);

return 0;
}

KMP

LibreOJ 对应模版题 代码。

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
/*
* Algorithm template : KMP
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>
#include <cstring>

const int MAXN = 1000005;

int fail[MAXN];
void calcFail(char *s) {
int n = strlen(s + 1);

fail[1] = 0;
for (int i = 2; i <= n; i++) {
int j = fail[i - 1];
while (j && s[j + 1] != s[i]) j = fail[j];
fail[i] = s[i] == s[j + 1] ? j + 1 : 0;
}
}

int kmp(char *s, char *t) {
int res = 0;
int n = strlen(s + 1), m = strlen(t + 1);

for (int i = 1, j = 0; i <= n; i++) {
while (j && t[j + 1] != s[i]) j = fail[j];
if (t[j + 1] == s[i]) j++;
if (j == m) {
res++;
j = fail[j]; // j = 0 when not allowed overlapping
}
}

return res;
}

int main() {
static char a[MAXN], b[MAXN];
scanf("%s %s", a + 1, b + 1);

calcFail(b);

printf("%d\n", kmp(a, b));

return 0;
}

数学

欧拉筛

  • $\mu$ :莫比乌斯函数
  • $\varphi$ :欧拉函数
  • $d$ :约数个数函数
  • $s$ :约数和函数
  • minFact :最小质因子的次幂的值,如 $minFact(12) = 4$。
  • minPow :最小质因子的次幂的幂值,如 $minPow(12) = 2$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
* Algorithm template : Euler Sieve (Linear Sieve)
*
* by: Pepcy_Ch
* time: 2017.7.11
*/

#include <cstdio>

const int MAXN = 10000005;

int prime[MAXN], primeCnt, mu[MAXN], phi[MAXN], d[MAXN];
long long s[MAXN];
bool notPrime[MAXN];

void eulerSieve() {
static int minFact[MAXN], minPow[MAXN];

notPrime[0] = notPrime[1] = true;
mu[1] = phi[1] = d[1] = s[1] = 1;
minFact[1] = minPow[1] = 1;

for (int i = 2; i < MAXN; i++) {
if (!notPrime[i]) {
prime[primeCnt++] = i;
mu[i] = -1;
phi[i] = i - 1;
d[i] = 2;
s[i] = i + 1;
minFact[i] = i;
minPow[i] = 1;
}

for (int j = 0; j < primeCnt && i * prime[j] < MAXN; j++) {
notPrime[i * prime[j]] = true;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
phi[i * prime[j]] = phi[i] * prime[j];
d[i * prime[j]] = d[i] / (minPow[i] + 1) * (minPow[i] + 2);
if (i == minFact[i]) s[i * prime[j]] = s[i] + i * prime[j];
else s[i * prime[j]] = s[i / minFact[i]] * s[prime[j] * minFact[i]];
minPow[i * prime[j]] = minPow[i] + 1;
minFact[i * prime[j]] = minFact[i] * prime[j];
break;
}
mu[i * prime[j]] = -mu[i];
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
d[i * prime[j]] = d[i] * 2;
s[i * prime[j]] = s[i] * s[prime[j]];
minPow[i * prime[j]] = 1;
minFact[i * prime[j]] = prime[j];
}
}
}

int main() {
eulerSieve();

return 0;
}

线性基

分为可在线插入数的版本和必需一口气插入所有数且之后不可再插入的版本。

在线版本为 LibreOJ 最大异或和代码。

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
/*
* Algorithm template : Max Xor-sum - Linear Basis (Online Edition)
*
* by: Pepcy_Ch
* time: 2017.7.11
*/

#include <cstdio>

const int MAXL = 50;

struct LinearBasis {
long long a[MAXL + 1];

bool extend(long long t) {
for (int i = MAXL; ~i; i--) {
if (!(t & (1ll << i))) continue;
if (!t) return false;

if (a[i]) t ^= a[i];
else {
for (int j = 0; j < i; j++) if (t & (1ll << j)) t ^= a[j];
for (int j = i + 1; j <= MAXL; j++) if (a[j] & (1ll << i)) a[j] ^= t;
a[i] = t;
return true;
}
}

return false;
}

long long queryMax() {
long long res = 0;
for (int i = 0; i <= MAXL; i++) res ^= a[i];
return res;
}
} lb;

int main() {
int n;
scanf("%d", &n);

for (int i = 0; i < n; i++) {
long long x;
scanf("%lld", &x);
lb.extend(x);
}

printf("%lld\n", lb.queryMax());

return 0;
}

离线版本为 LibreOJ k 大异或和代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
* Algorithm template : kth Max Xor-sum - Linear Basis (Offline Edition)
*
* by: Pepcy_Ch
* time: 2017.7.11
*/

#include <cstdio>
#include <vector>
#include <algorithm>

const int MAXN = 100005;
const int MAXL = 50;

struct LinearBasis {
std::vector<long long> v;
int n;

void init(long long *x, int n) {
this->n = n;
static long long a[MAXL + 1];

for (int i = 0; i < n; i++) {
long long t = x[i];

for (int j = MAXL; ~j; j--) {
if (!(t & (1ll << j))) continue;
if (!t) break;

if (a[j]) t ^= a[j];
else {
for (int k = 0; k < j; k++) if (t & (1ll << k)) t ^= a[k];
for (int k = j + 1; k <= MAXL; k++) if (a[k] & (1ll << j)) a[k] ^= t;
a[j] = t;
break;
}
}
}

v.clear();
for (int i = 0; i <= MAXL; i++) if (a[i]) v.push_back(a[i]);
}

long long query(int k) {
if (v.size() != n) k--;
if (k >= (1ll << v.size())) return -1;

long long res = 0;
for (int i = 0; i < v.size(); i++) if (k & (1ll << i)) res ^= v[i];
return res;
}
} lb;

int main() {
int n;
scanf("%d", &n);

static long long a[MAXN];
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
lb.init(a, n);

int q;
scanf("%d", &q);
while (q--) {
long long k;
scanf("%lld", &k);
printf("%lld\n", lb.query(k));
}
return 0;
}

高斯消元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
* Algorithm template : Guass-Jordan Elimination
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAXN = 105;
const double EPS = 1e-6;

namespace GuassJordan {
double a[MAXN][MAXN];

bool solve(int n) {
for (int i = 0; i < n; i++) {
int max = i;
for (int j = i + 1; j < n; j++) if (fabs(a[j][i]) > fabs(a[max][i])) max = j;
if (fabs(a[max][i]) < EPS) return false;
if (max != i) for (int j = i; j <= n; j++) std::swap(a[i][j], a[max][j]);
for (int j = 0; j < n; j++) if (i != j)
for (int k = n; k >= i; k--) a[j][k] -= a[i][k] / a[i][i] * a[j][i];
}
return true;
}
}

int main() {
int n;
scanf("%d", &n);

using GuassJordan::a;

for (int i = 0; i < n; i++) for (int j = 0; j <= n; j++) scanf("%lf", &a[i][j]);

if (!GuassJordan::solve(n)) {
puts("-1");
} else {
for (int i = 0; i < n; i++) printf("%.4lf\n", a[i][n] / a[i][i]);
}

return 0;
}

FFT/NTT

两个都是 LibreOJ 对应模版题代码。

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
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
/*
* Algorithm template : Fast Fourier Transform
*
* by: Pepcy_Ch
* time: 2017.7.14
*/

#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAXN = 100005;
const int MAXN_EXTEND = 262144;
const double PI = acos(-1);

struct Complex {
double r, i;

Complex(double r = 0, double i = 0) : r(r), i(i) {}

Complex conj() const {
return Complex(r, -i);
}

Complex operator+(const Complex &rhs) const {
return Complex(r + rhs.r, i + rhs.i);
}
Complex &operator+=(const Complex &rhs) {
return *this = *this + rhs;
}

Complex operator-(const Complex &rhs) const {
return Complex(r - rhs.r, i - rhs.i);
}

Complex operator*(const Complex &rhs) const {
return Complex(r * rhs.r - i * rhs.i, r * rhs.i + i * rhs.r);
}
Complex &operator*=(const Complex &rhs) {
return *this = *this * rhs;
}

Complex operator/(const double rhs) const {
return Complex(r / rhs, i / rhs);
}
Complex &operator/=(const double rhs) {
return *this = *this / rhs;
}
};

namespace FFT {
static const int N = 262144;

Complex omega[N], omegaInv[N];

void init() {
for (int i = 0; i < N; i++) {
omega[i] = Complex(cos(2 * PI * i / N), sin(2 * PI * i / N));
omegaInv[i] = omega[i].conj();
}
}

int extend(int n) {
int res = 1;
while (res < n) res <<= 1;
return res;
}

void reverse(Complex *a, int n) {
for (int i = 0, j = 0; i < n; i++) {
if (i < j) std::swap(a[i], a[j]);
for (int l = n >> 1; (j ^= l) < l; l >>= 1) {}
}
}

void transform(Complex *a, int n, Complex *omega) {
reverse(a, n);

for (int l = 2; l <= n; l <<= 1) {
int hl = l >> 1;
for (Complex *x = a; x != a + n; x += l) {
for (int i = 0; i < hl; i++) {
Complex t = omega[N / l * i] * x[i + hl];
x[i + hl] = x[i] - t;
x[i] += t;
}
}
}
}

void dft(Complex *a, int n) {
transform(a, n, omega);
}

void idft(Complex *a, int n) {
transform(a, n, omegaInv);
for (int i = 0; i < n; i++) a[i] /= n;
}
}

int main() {
int n, m;
scanf("%d %d", &n, &m);

static Complex a[MAXN_EXTEND], b[MAXN_EXTEND];
for (int i = 0; i <= n; i++) scanf("%lf", &a[i].r);
for (int i = 0; i <= m; i++) scanf("%lf", &b[i].r);

FFT::init();
int N = FFT::extend(n + m + 1);

FFT::dft(a, N);
FFT::dft(b, N);
for (int i = 0; i < N; i++) a[i] *= b[i];
FFT::idft(a, N);

for (int i = 0; i < n + m + 1; i++) printf("%.0lf%c", a[i].r + 0.001, " \n"[i == n + m]);

return 0;
}

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
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
/*
* Algorithm template : Number Theoretic Transform
*
* by: Pepcy_Ch
* time: 2017.7.14
*/

#include <cstdio>
#include <algorithm>

const int MAXN = 100005;
const int MAXN_EXTEND = 262144;
const int MOD = 998244353;
const int G = 3;

long long pow(long long a, long long n) {
long long res = 1;
for (; n; n >>= 1, a = a * a % MOD) if (n & 1) res = res * a % MOD;
return res;
}

void exgcd(long long a, long long b, long long &x, long long &y) {
if (!b) x = 1, y = 0;
else exgcd(b, a % b, y, x), y -= x * (a / b);
}

long long inv(long long x) {
long long res, temp;
exgcd(x, MOD, res, temp);
return (res % MOD + MOD) % MOD;
}

namespace NTT {
static const int N = 262144;

long long omega[N], omegaInv[N];

void init() {
long long g = pow(G, (MOD - 1) / N), ig = inv(g);
omega[0] = omegaInv[0] = 1;
for (int i = 1; i < N; i++) {
omega[i] = omega[i - 1] * g % MOD;
omegaInv[i] = omegaInv[i - 1] * ig % MOD;
}
}

int extend(int n) {
int res = 1;
while (res < n) res <<= 1;
return res;
}

void reverse(long long *a, int n) {
for (int i = 0, j = 0; i < n; i++) {
if (i < j) std::swap(a[i], a[j]);
for (int l = n >> 1; (j ^= l) < l; l >>= 1) {}
}
}

void transform(long long *a, int n, long long *omega) {
reverse(a, n);

for (int l = 2; l <= n; l <<= 1) {
int hl = l >> 1;
for (long long *x = a; x != a + n; x += l) {
for (int i = 0; i < hl; i++) {
long long t = omega[N / l * i] * x[i + hl] % MOD;
x[i + hl] = (x[i] - t + MOD) % MOD;
x[i] += t;
x[i] >= MOD ? x[i] -= MOD : 0;
}
}
}
}

void dft(long long *a, int n) {
transform(a, n, omega);
}

void idft(long long *a, int n) {
transform(a, n, omegaInv);
long long t = inv(n);
for (int i = 0; i < n; i++) (a[i] *= t) %= MOD;
}
}

int main() {
int n, m;
scanf("%d %d", &n, &m);

static long long a[MAXN_EXTEND], b[MAXN_EXTEND];
for (int i = 0; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 0; i <= m; i++) scanf("%lld", &b[i]);

NTT::init();
int N = NTT::extend(n + m + 1);

NTT::dft(a, N);
NTT::dft(b, N);
for (int i = 0; i < N; i++) (a[i] *= b[i]) %= MOD;
NTT::idft(a, N);

for (int i = 0; i < n + m + 1; i++) printf("%lld%c", a[i], " \n"[i == n + m]);

return 0;
}

线性预处理逆元

线性预处理 $1, 2, \dots n$ 和 $1!, 2!, \dots n!$ 的逆元。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
* Algorithm template : Get Inverse Lnearly (Inverse of [1...n] and fact[1]...fact[n])
*
* by: Pepcy_Ch
* time: 2017.7.11
*/

#include <cstdio>

const int MAXN = 3000005;

int fact[MAXN], invFact[MAXN], inv[MAXN];

void exgcd(int a, int b, int &x, int &y) {
if (b == 0) x = 1, y = 0;
else exgcd(b, a % b, y, x), y -= x * (a / b);
}

int getInv(int x, int mod) {
int res, temp;
exgcd(x, mod, res, temp);
return res;
}

int main() {
int n, p;
scanf("%d %d", &n, &p);

inv[1] = 1;
for (int i = 2; i <= n; i++) inv[i] = (long long) (p - p / i) * inv[p % i] % p;
for (int i = 1; i <= n; i++) printf("%d%c", inv[i], " \n"[i == n]);

fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = (long long) fact[i - 1] * i % p;
invFact[n] = getInv(fact[n], p);
for (int i = n - 1; i; i--) inv[i] = (long long) (i + 1) * invFact[i + 1] % p;
for (int i = 1; i <= n; i++) printf("%d%c", invFact[i], " \n"[i == n]);

return 0;
}

组合数预处理与 Lucas 定理

预处理。

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
/*
* Algorithm template : Combination Initialize
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>

const int MAXN = 10005;
const int MOD = 998244353;

int _combi[MAXN][MAXN];

void prepare() {
for (int i = 1; i < MAXN; i++) {
_combi[i][0] = _combi[i][i] = 1;
for (int j = 1; j < i; j++) _combi[i][j] = (_combi[i - 1][j - 1] + _combi[i - 1][j]) % MOD;
}
}

int combi(int n, int m) {
if (n < MAXN) return _combi[n][m];

return -1;
}

int main() {
prepare();

return 0;
}

Lucas 定理。

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
/*
* Algorithm template : Lucas Theory
*
* by: Pepcy_Ch
* time: 2017.7.12
*/

#include <cstdio>

const int MOD = 1000003;

int fact[MOD], inv[MOD];

long long pow(long long a, long long n) {
long long res = 1;
for (; n; n >>= 1, a = a * a % MOD) if (n & 1) res = res * a % MOD;
return res;
}

void prepare() {
fact[0] = 1;
for (int i = 1; i < MOD; i++) fact[i] = (long long) fact[i - 1] * i % MOD;

inv[MOD - 1] = pow(fact[MOD - 1], MOD - 2);
for (int i = MOD - 2; i; i--) inv[i] = (long long) inv[i + 1] * (i + 1) % MOD;
}

int combi(int n, int m) {
if (m > n) return 0;
if (n < MOD) return (long long) fact[n] * inv[m] % MOD * inv[n - m] % MOD;
return (long long) combi(n / MOD, m / MOD) * combi(n % MOD, m % MOD) % MOD;
}

int main() {
prepare();

return 0;
}

其他/不会分类

三维偏序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/*
* Algorithm template : CDQ Divide;
*
* by: Pepcy_Ch
* time: 2017.7.15
*/

#include <cstdio>
#include <algorithm>

const int MAXN = 100005;
const int MAXK = 200005;

struct Data {
int a, b, c, cnt, ans;

bool operator<(const Data &rhs) const {
return a < rhs.a || (a == rhs.a && b < rhs.b)
|| (a == rhs.a && b == rhs.b && c < rhs.c);
}
} a[MAXN];

struct BinaryIndexedTree {
int c[MAXK], n;

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

void init(int n) {
this->n = n;
}

void update(int pos, int d) {
for (int i = pos; i <= n; i += lowbit(i)) c[i] += d;
}

int query(int pos) {
int res = 0;
for (int i = pos; i; i -= lowbit(i)) res += c[i];
return res;
}

void clear(int pos) {
for (int i = pos; i <= n; i += lowbit(i)) {
if (c[i]) c[i] = 0;
else break;
}
}
} bit;

void divide(Data *l, Data *r) {
if (l == r) {
l->ans += l->cnt - 1;
return;
}

Data *mid = l + (r - l) / 2;
divide(l, mid), divide(mid + 1, r);

static Data temp[MAXN];
for (Data *p = temp, *pl = l, *pr = mid + 1; p <= temp + (r - l); p++) {
if (pr > r || (pl <= mid && pl->b <= pr->b)) {
*p = *pl++;
bit.update(p->c, p->cnt);
} else {
*p = *pr++;
p->ans += bit.query(p->c);
}
}

for (Data *p = temp, *q = l; q <= r; q++, p++) {
bit.clear(q->c);
*q = *p;
}
}

int main() {
int n, k;
scanf("%d %d", &n, &k);

for (int i = 0; i < n; i++)
scanf("%d %d %d", &a[i].a, &a[i].b, &a[i].c), a[i].cnt = 1;

std::sort(a, a + n);
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i && a[i].a == a[i - 1].a && a[i].b == a[i - 1].b && a[i].c == a[i - 1].c)
a[cnt - 1].cnt++;
else a[cnt++] = a[i];
}

bit.init(k);
divide(a, a + cnt - 1);

static int ans[MAXN];
for (int i = 0; i < cnt; i++) ans[a[i].ans] += a[i].cnt;
for (int i = 0; i < n; i++) printf("%d\n", ans[i]);

return 0;
}