模板

普通模板

1
2
3
4
5
6
7
#include <iostream>
using namespace std;
int main() {

system("pause");
return 0;
}

快读模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;
inline int read(){
int s=0,f=1;
char ch=getchar();
while(!isdigit(ch)) f = (ch=='-'?-1:1),ch = getchar();
while(isdigit(ch)) s = s * 10 + (ch ^ 48),ch = getchar();
return s*f;
}
int main() {

system("pause");
return 0;
}

字符串Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
typedef unsigned long long ull;
const int mul = 131;
string a, b;
ull p[1000010], h[1000010], hb;
int res;
inline ull seghash(int s, int n) {
return h[s] - h[s + n] * p[n];
}
int main() {
cin >> a >> b;
p[0] = 1;
for(int i = 1; i <= 1000000; i++) p[i] = p[i - 1] * mul;
for(int i = a.size(); i >= 0; i--) h[i] = h[i + 1] * mul + a[i];
for(int i = b.size(); i >= 0; i--) hb = hb * mul + b[i];
for(int i = 0; i <= a.size() - b.size() + 1; i++) {
if(seghash(i, b.size()) == hb) res++;
}
cout << res << endl;
system("pause");
return 0;
}

KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
string s, p;
int fail[1000010];
void getFail() {
for(int i = 1, k = fail[0] = 0; i < p.size(); i++) {
while(k && p[i] != p[k]) k = fail[k - 1];
fail[i] = k = p[i] == p[k] ? k + 1 : k;
}
}
int kmp() {
for(int i = 0, j = 0; i < s.size(); i++) {
while(j && s[i] != p[j]) j = fail[j - 1];
if(j = s[i] == p[j] ? j + 1 : j == p.size()) return i - j + 1;
}
return -1;
}
int main() {
cin >> s >> p;
getFail();
cout << kmp() << endl;
system("pause");
return 0;
}

Manacher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <iostream>
using namespace std;
string str;
int p[2000010];
string pretreatment(string raw) {
string s;
s = "^";
for(int i = 0; i < raw.size(); i++)
s = s + '#' + raw[i];
s += "#$";
return s;
}
int manacher(string s) {
int r = 0, center = 0;
for(int i = 1; i < s.size() - 1; i++) {
int mirror = center * 2 - i;
p[i] = r <= i ? 0 : min(r - i, p[mirror]);
while(s[i - p[i] - 1] == s[i + p[i] + 1]) p[i]++;
if(i + p[i] > r) center = i, r = i + p[i];
}
return *max_element(p + 1, p + s.size());
}
int main() {
cin >> str;
str = pretreatment(str);
cout << manacher(str) << endl;
system("pause");
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
#include <iostream>
#include <queue>
using namespace std;
const int root = 0;
int n, ch[1000010][26], fail[1000010], cnt[1000010], len;
string t;
void insert(string str) {
int p = root;
for(auto c : str) {
if(!ch[p][c - 'a']) ch[p][c - 'a'] = ++len;
p = ch[p][c - 'a'];
}
cnt[p]++;
}
void build() {
queue<int> q;
for(int i = 0; i < 26; i++)
if(ch[root][i]) q.push(ch[root][i]);
while(q.size()) {
int p = q.front();
q.pop();
for(int i = 0; i < 26; i++) {
if(ch[p][i]) fail[ch[p][i]] = ch[fail[p]][i], q.push(ch[p][i]);
else ch[p][i] = ch[fail[p]][i];
}
}
}
int match() {
int p = root, res = 0;
for(auto c : t) {
p = ch[p][c - 'a'];
for(int i = p; i && cnt[i] != -1; i = fail[i]) {
res += cnt[i], cnt[i] = -1;
}
}
return res;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
string p;
cin >> p;
insert(p);
}
cin >> t;
build();
cout << match() << endl;
system("pause");
return 0;
}

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
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
#include <iostream>
#include <random>
using namespace std;
mt19937 mt(random_device {}());
int root = 0, len = 1, val[100010], lc[100010], rc[100010], sz[100010], w[100010];
inline int newNode(int v) {
val[len] = v;
sz[len] = 1;
w[len] = mt();
lc[len] = rc[len] = 0;
return len++;
}
inline void updateSize(int p) {
sz[p] = sz[lc[p]] + sz[rc[p]] + 1;
}
void LDR(int id) {
if(!id) return;
LDR(lc[id]);
cout << val[id] << ' ';
LDR(rc[id]);
}
void split(int id, int k, int &x, int &y) {
if(!id) {
x = y = 0;
return;
}
if(val[id] <= k) {
x = id;
split(rc[id], k, rc[id], y);
} else {
y = id;
split(lc[id], k, x, lc[id]);
}
updateSize(id);
}
int merge(int x, int y) {
if(!x || !y) return x + y;
if(w[x] > w[y]) {
rc[x] = merge(rc[x], y);
updateSize(x);
return x;
} else {
lc[y] = merge(x, lc[y]);
updateSize(y);
return y;
}
}
void insert(int v) {
int x, y;
split(root, v, x, y);
root = merge(merge(x, newNode(v)), y);
}
void erase(int v) {
int x, y, z;
split(root, v, x, z);
split(x, v - 1, x, y);
if(y) y = merge(lc[y], rc[y]);
root = merge(merge(x, y), z);
}
int rnk(int v) {
int x, y, res;
split(root, v - 1, x, y);
res = sz[x] + 1;
root = merge(x, y);
return res;
}
int kth(int k) {
int p = root;
while(p) {
if(sz[lc[p]] + 1 == k) return val[p];
if(sz[lc[p]] >= k) p = lc[p];
else k -= sz[lc[p]] + 1, p = rc[p];
}
return -1;
}
int pre(int v) {
int x, y, p, res = -2147483647;
split(root, v - 1, x, y);
p = x;
while(p) res = val[p], p = rc[p];
root = merge(x, y);
return res;
}
int nxt(int v) {
int x, y, p, res = 2147483647;
split(root, v, x, y);
p = y;
while(p) res = val[p], p = lc[p];
root = merge(x, y);
return res;
}
int main() {
int n;
cin >> n;
while(n--) {
int opt, x;
cin >> opt >> x;
switch(opt) {
case 1:
insert(x);
break;
case 2:
erase(x);
break;
case 3:
cout << rnk(x) << endl;
break;
case 4:
cout << kth(x) << endl;
break;
case 5:
cout << pre(x) << endl;
break;
case 6:
cout << nxt(x) << endl;
break;
}
}
system("pause");
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
#include <algorithm>
#include <iostream>
#define lchild(x) x<<1
#define rchild(x) x<<1|1
#define father(x) x>>1
using namespace std;
const int MAXN = 4 * 1000010, inf = 0x3f3f3f3f;
int n, arr[MAXN], minv[MAXN];
inline void pushup(int id) {
minv[id] = min(minv[lchild(id)], minv[rchild(id)]);
}
void build(int id, int l, int r) {
if(l == r) {
minv[id] = arr[l];
return;
}
int mid = (l + r) >> 1;
build(lchild(id), l, mid);
build(rchild(id), mid + 1, r);
pushup(id);
}
int query(int id, int l, int r, int x, int y) {
if(x <= l && r <= y) return minv[id];
int mid = (l + r) >> 1;
int ans = inf;
if(x <= mid) ans = min(ans, query(lchild(id), l, mid, x, y));
if(y > mid) ans = min(ans, query(rchild(id), mid + 1, r, x, y));
return ans;
}
void update(int id, int index, int val, int l, int r) {
if(l == r) {
minv[id] = arr[index] = val;
return;
}
int mid = (l + r) >> 1;
if(index <= mid) update(lchild(id), index, val, l, mid);
else update(rchild(id), index, val, mid + 1, r);
pushup(id);
}
int t;
int main() {
cin >> n >> t;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
}
build(1, 1, n);
while(t--) {
int op;
cin >> op;
switch(op) {
case 1:
int l, r;
cin >> l >> r;
cout << query(1, 1, n, l, r) << endl;
break;
case 2:
int index, val;
cin >> index >> val;
update(1, index, val, 1, n);
break;
}
}
system("pause");
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
#include <algorithm>
#include <iostream>
#define lchild(x) x<<1
#define rchild(x) x<<1|1
#define father(x) x>>1
using namespace std;
/*
2021/2/21
lazy-tag 区间修改,区间查询,快读+long long
*/
const int MAXN = 4 * 1000010, inf = 0x3f3f3f3f;
int n, l[MAXN], r[MAXN];
long long arr[MAXN], sum[MAXN], tag[MAXN];
inline void pushup(int id) {
sum[id] = sum[lchild(id)] + sum[rchild(id)];
}
inline void pushdown(int id) {
if(tag[id]) {
tag[lchild(id)] += tag[id];
tag[rchild(id)] += tag[id];
sum[lchild(id)] += tag[id] * (r[lchild(id)] - l[lchild(id)] + 1);
sum[rchild(id)] += tag[id] * (r[rchild(id)] - l[rchild(id)] + 1);
tag[id] = 0;
}
}
void build(int id) {
if(l[id] == r[id]) {
sum[id] = arr[l[id]];
return;
}
int mid = (l[id] + r[id]) >> 1;
l[lchild(id)] = l[id];
r[lchild(id)] = mid;
l[rchild(id)] = mid + 1;
r[rchild(id)] = r[id];
build(lchild(id));
build(rchild(id));
pushup(id);
}
long long query(int id, int x, int y) {
if(x <= l[id] && r[id] <= y) return sum[id];
pushdown(id);
int mid = (l[id] + r[id]) >> 1;
long long ans = 0;
if(x <= mid) ans = ans + query(lchild(id), x, y);
if(y > mid) ans = ans + query(rchild(id), x, y);
return ans;
}
void update(int id, int v, int x, int y) {
if(x <= l[id] && r[id] <= y) {
tag[id] += v;
sum[id] += v * (r[id] - l[id] + 1);
return;
}
pushdown(id);
int mid = (l[id] + r[id]) >> 1;
if(x <= mid) update(lchild(id), v, x, y);
if(y > mid) update(rchild(id), v, x, y);
pushup(id);
}
long long read() {
long long s = 0;
int f = 1;
char ch;
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
int t;
int main() {
cin >> n >> t;
for(int i = 1; i <= n; i++) {
arr[i] = read();
}
l[1] = 1, r[1] = n;
build(1);
while(t--) {
int op;
cin >> op;
switch(op) {
case 1: {
int l, r;
cin >> l >> r;
cout << query(1, l, r) << endl;
break;
}
case 2: {
int l, r, val;
cin >> l >> r >> val;
update(1, val, l, r);
break;
}
}
}
system("pause");
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
#include <algorithm>
#include <iostream>
#define lchild(x) x<<1
#define rchild(x) x<<1|1
#define father(x) x>>1
using namespace std;
const int MAXN = 4 * 1000010, inf = 0x3f3f3f3f;
int n, arr[MAXN], sum[MAXN];
inline void pushup(int id) {
sum[id] = sum[lchild(id)] + sum[rchild(id)];
}
void build(int id, int l, int r) {
if(l == r) {
sum[id] = arr[l];
return;
}
int mid = (l + r) >> 1;
build(lchild(id), l, mid);
build(rchild(id), mid + 1, r);
pushup(id);
}
int query(int id, int l, int r, int x, int y) {
if(x <= l && r <= y) return sum[id];
int mid = (l + r) >> 1;
int ans = 0;
if(x <= mid) ans = ans + query(lchild(id), l, mid, x, y);
if(y > mid) ans = ans + query(rchild(id), mid + 1, r, x, y);
return ans;
}
void update(int id, int index, int val, int l, int r) {
if(l == r) {
sum[id] = arr[index] = val;
return;
}
int mid = (l + r) >> 1;
if(index <= mid) update(lchild(id), index, val, l, mid);
else update(rchild(id), index, val, mid + 1, r);
pushup(id);
}
int t;
int main() {
cin >> n >> t;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
}
build(1, 1, n);
while(t--) {
int op;
cin >> op;
switch(op) {
case 1:
int l, r;
cin >> l >> r;
cout << query(1, 1, n, l, r) << endl;
break;
case 2:
int index, val;
cin >> index >> val;
update(1, index, val, 1, n);
break;
}
}
system("pause");
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
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 4 * 1000010, inf = 0x3f3f3f3f;
int n, sum[MAXN];
inline int lowbit(int x) {
return x & (-x);
}
inline int query_1tox(int x) {
int res = 0;
for(int i = x; i > 0; i -= lowbit(i)) {
res += sum[i];
}
return res;
}
inline int query(int l, int r) {
return query_1tox(r) - query_1tox(l - 1);
}
inline void update(int index, int val) {
for(int i = index; i <= n; i += lowbit(i)) {
sum[i] += val;
}
}
int t;
int main() {
cin >> n >> t;
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
update(i, x);
}
while(t--) {
int op;
cin >> op;
switch(op) {
case 1:
int l, r;
cin >> l >> r;
cout << query(l, r) << endl;
break;
case 2:
int index, val;
cin >> index >> val;
update(index, val);
break;
}
}
system("pause");
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
#include <iostream>
#include <cstring>
#include <bitset>
#include <list>
#include <set>
#define distance first
#define node second
using namespace std;
const int inf = 0x3f3f3f3f;
bitset<100010> vis;
list<pair<int, int> > edges[100010];
int n, m, s, dist[100010];
set<pair<int, int> > pq;
void dijkstra() {
dist[s] = 0;
pq.insert({0, s});
while(pq.size()) {
auto v = *pq.begin();
pq.erase(pq.begin());
for(auto edge : edges[v.node]) {
if(dist[edge.node] > dist[v.node] + edge.distance) {
pq.erase({dist[edge.node], edge.node});
dist[edge.node] = dist[v.node] + edge.distance;
pq.insert({dist[edge.node], edge.node});
}
}
}
}
int main() {
memset(dist, inf, sizeof(dist));
cin >> n >> m >> s;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges[u].push_back({w, v});
}
dijkstra();
for(int i = 1; i <= n; i++) {
cout << (dist[i] == inf ? 2147483647 : dist[i]) << ' ';
}
cout << endl;
system("pause");
return 0;
}

模板
https://www.d0j1a1701.cc/p/f6010553/
作者
d0j1a_1701
发布于
2021年5月3日
许可协议
CC-BY-SA