代码模板Template

数学

扩展欧几里德算法

贝祖定理:对于任意整数$a,b$,存在一对整数$x,y$满足$ax+by=gcd(a,b)$。

证明:

  • 显然,存在$x=1,y=0$使得$a1+00=gcd(a,0)$成立

  • 若$b>0$,则有$gcd(a,b)=gcd(b,a \mod b)$。

  • 假设存在一对整数$x,y$使得$bx+(a \mod b)y=gcd(b,a \mod b)$

  • $bx+(a \mod b)y=bx+(a-b(\frac ab))*y=ay+b(x-y(\frac ab))$

  • 令$x’=y,y’=x-y(\frac ab)$,则$ax’+by’=gcd(a,b)$

  • 对欧几里德算法的递归过程进行数学归纳,可知定理成立

贝祖定理是按照欧几里德算法的思路证明的,且同时给出了$x,y$的计算方法。我们称其为扩展欧几里德算法。

Code

1
2
3
4
5
6
7
8
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1; y = 0; return a;
}
ll r = exgcd(b, a % b, x, y);
ll t = x; x = y; y = t - a / b * y;
return r;
}

上述程序可求$ax+by=gcd(a,b)$的一组特解$x_0,y_0$,并返回最大公约数$r$。

对于一般方程$ax+by=c$,它有解当且仅当$r|c$。我们对特解$x_0,y_0$同时乘上$\frac cr$,即可得到一组特解$\frac crx_0,\frac cry_0$。

由此我们可得通解$x=\frac crx_0+k\frac br,y=\frac cry_0-k\frac ar(k\in Z)$

动态规划

二分优化的lis

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
int f[300100];
int g[300100];
int a[300100];

int binary(int x) {
int lf = 0, rt = k, mid;
while (lf + 1 < rt) {
mid = ((lf + rt) >> 1);
if (g[mid] < x) lf = mid;
else rt = mid;
}
if (g[rt] < x) lf = rt;
return lf;
}

void solution() {
f[1] = 1;
g[1] = a[1];
k = 1;
for (int i = 2; i <= n; i++) {
if (a[i] > g[k]) {
k++;
g[k] = a[i];
f[i] = k;
}
else {
int t = binary(a[i]);
f[i] = t + 1;
if (g[t + 1] > a[i]) g[t + 1] = a[i];
}
}
printf("%d\n", k);
}

图论

最短路

堆优化的dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef pair<int, int> pii;
void dijkstra() {
priority_queue<pii, vector<pii>, greater<pii> > Q;
memset(dis, 10, sizeof(dis));
dis[s] = 0;
memset(vis, 0, sizeof(vis));
Q.push(make_pair(dis[s], s));
while (!Q.empty()) {
pii temp = Q.top();
Q.pop();
int x = temp.second;
if (vis[x]) continue;
vis[x] = 1;
for (int i = lin[x]; i; i = e[i].nt) {
if (dis[e[i].y] > dis[x] + e[i].v) {
dis[e[i].y] = dis[x] + e[i].v;
Q.push(make_pair(dis[e[i].y], e[i].y));
}
}
}
}

Tarjan

强连通分量缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void tarjan(int x) {
dfn[x] = low[x] = ++tim;
vis[stack[++top] = x] = 1;
for (int i = lin[x]; i; i = e[i].nt) {
int y = e[i].y;
if (!dfn[y]) {
tarjan(y);
low[x] = std::min(low[x], low[y]);
}
else if (vis[y]) low[x] = std::min(low[x], dfn[y]);
}
if (low[x] == dfn[x]) {
int k;
++num;
do {
k = stack[top--];
bel[k] = num;
vis[k] = 0;
} while (k != x);
}
}

割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int tarjan(int x, int father = 0) {
int cnt = 0;
dfn[x] = low[x] = ++tim;
for (int i = lin[x]; i; i = e[i].nt) {
int y = e[i].y;
if (!dfn[y]) {
tarjan(y, x);
low[x] = std::min(low[x], low[y]);
if (low[y] >= dfn[x]) ++cnt;
}
else low[x] = std::min(low[x], dfn[y]);
}
if (cnt >= 2 || (father && cnt == 1)) ans[++tail] = x;
}

割边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void tarjan(int x, int par = 0) {
dfn[x] = low[x] = ++tim;
for (int i = lin[x]; i; i = e[i].nt) {
int y = e[i].y;
if (i != par) {
if (!dfn[y]) {
tarjan(y, rev[i]);
low[x] = min(low[x], low[y]);
}
else low[x] = min(low[x], dfn[y]);
}
}
if (dfn[x] == low[x]) ans[++tail] = par;
}

网络流

DFS

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
void dfs(int id, int v) {
f[id] = 1;
if (id == n) {
flag = 1;
ans += v;
fwd = v;
return;
}
for (int i = 1; i <= n; i++) {
if (a[id][i] > 0 && !f[i]) {
dfs(i, std::min(v, a[id][i]));
if (flag) {
a[id][i] -= fwd;
a[i][id] += fwd;
return;
}
}
}
}

void work() {
while (flag) {
flag = false;
memset(f, 0, sizeof(f));
dfs(1, oo);
}
printf("%d", ans);
}

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
bool make_level() {
memset(level, -1, sizeof(level));
level[1] = 0;
q[1] = 1;
head = 0;
tail = 1;
while (head++ < tail) {
int x = q[head];
for (int i = lin[x]; i; i = e[i].nt) {
if (e[i].v && level[e[i].y] == -1) {
q[++tail] = e[i].y;
level[e[i].y] = level[x] + 1;
}
}
}
return level[n*m] >= 0;
}

int max_flow(int k, int flow) {
if (k == n*m) return flow;
int maxflow = 0;
int d = 0;
for (int i = lin[k]; i && (maxflow < flow); i = e[i].nt) {
if (level[e[i].y] == level[k] + 1 && e[i].v) {
if (d = max_flow(e[i].y, min(flow - maxflow, e[i].v))) {
maxflow += d;
e[i].v -= d;
e[rev[i]].v += d;
}
}
}
if (!maxflow) level[k] = -1;
return maxflow;
}

void dinic() {
int ans = 0;
int d = 0;
while (make_level())
while (d = max_flow(1, INF))
ans += d;
cout << ans << endl;
}

字符串

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
25
26
void getp(char *b) {
p[1] = 0;
int j = 0;
int len = strlen(b + 1);
for (int i = 2; i <= len; ++i){
while (j > 0 && b[j + 1] != b[i]) j = p[j];
if (b[j + 1] == b[i]) j++;
p[i] = j;
}
}

int kmp(char *a, char *b) {
int sum = 0;
int j = 0;
int len = strlen(a + 1);
int r = strlen(b + 1);
for (int i = 1; i <= len; ++i) {
while (j > 0 && b[j + 1] != a[i]) j = p[j];
if (b[j + 1] == a[i]) ++j;
if (j == r){
sum += val[id] * (i - r + 1);
j = p[j];
}
}
return sum;
}

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
void add_node(int k, int node) {
int ch = s[k] - 'a';
if (!trie[node].lin[ch]) {
trie[node].lin[ch] = ++len;
trie[len].end = 0;
trie[len].fail = 0;
}
if (k == slen) {
trie[node].end = 1;//++trie[node].end;
return;
}
add_node(k+1, trie[node].lin[ch]);
}

void build_fail() {
head = tail = 0;
q[tail] = 0;
while (head <= tail) {
int node = q[head++];
int temp;
for (int i = 0; i < 26; ++i) {
if (trie[node].lin[i]) {
int nt = trie[node].lin[i];
if (node) {
temp = trie[node].fail;
while (!trie[temp].lin[i] && temp)
temp = trie[temp].fail;
trie[nt].fail = trie[temp].lin[i];
}
q[++tail] = nt;
}
}
}
}

void find() {
ans = 0;
int node = 0;
for (int i = 1; i <= len; ++i) {
int ch = s[i] - 'a';
while (!trie[node].lin[ch] && node)
node = trie[node].fail;
node = tire[node].lin[ch];
int temp = node;
while (temp) {
if (trie[temp].end >= -1) {
ans += trie[temp].end;
trie[temp].end = -1;
}
temp = trie[temp].fail;
}
}
printf("%d\n",ans);
}

后缀数组

倍增算法

rank:x的排名

sa:排第x的下标

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
bool rua(int x, int y, int l) {
return rank[x] == rank[y] && rank[x + l] == rank[y + l];
}

void doubling() {
m = 260;
for (int i = 1; i <= n; ++i) ++cnt[rank[i] = s[i]];
for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (int i = n; i; --i) sa[cnt[rank[i]]--] = i;
for (int i, l = 1, k = 0; k < n; m = k) {
for (k = 0,i = n - l + 1; i <= n; ++i) p[++k] = i;
for (i = 1; i <= n; ++i) if(sa[i] > l) p[++k] = sa[i] - l;
for (i = 1; i <= m; ++i) cnt[i] = 0;
for (i = 1; i <= n; ++i) ++cnt[rank[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i; --i) sa[cnt[rank[p[i]]]--] = p[i];
for (k = 0, i = 1; i <= n; ++i)
temp[sa[i]] = rua(sa[i], sa[i-1], l) ? k : ++k;
for (i = 1; i <= n; ++i) rank[i] = temp[i];
l <<= 1;
}
for (int i = 1; i <= n; ++i) rank[sa[i]] = i;

for (int i = 1, j = 0, k; i <= n; ++i) {
if (!(k = sa[rank[i] - 1])) {
j = 0;
continue;
}
if (j) --j;
while (s[k + j] == s[i + j]) ++j;
height[rank[i]] = j;
}
}

数据结构

线段树

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
struct qaq{
ll maxx, deladd;
ll delx;
}tree[maxn * 4];

void push_down(ll id, ll l, ll r) {
if (tree[id].delx == 1 && tree[id].deladd == 0) return;
ll tad = tree[id].deladd;
ll txx = tree[id].delx;
ll mid = (l + r) >> 1;
tree[L(id)].deladd = (tree[L(id)].deladd * txx + tad) % mo;
tree[R(id)].deladd = (tree[R(id)].deladd * txx + tad) % mo;
tree[L(id)].delx = (tree[L(id)].delx * txx) % mo;
tree[R(id)].delx = (tree[R(id)].delx * txx) % mo;
tree[L(id)].maxx = (tree[L(id)].maxx * txx + (mid - l + 1) * tad) % mo;
tree[R(id)].maxx = (tree[R(id)].maxx * txx + (r - mid) * tad) % mo;
tree[id].deladd = 0;
tree[id].delx = 1;
return;
}

void build(ll l, ll r, ll id, ll v) {
if (l > y || r < x) return;
tree[id].delx = 1;
tree[id].deladd = 0;
if (x <= l && r <= y) {
tree[id].maxx = v;
return;
}
ll mid = (l + r) >> 1;
build(l, mid, L(id), v);
build(mid + 1, r, R(id), v);
tree[id].maxx = (tree[L(id)].maxx + tree[R(id)].maxx) % mo;
return;
}

void updatax(ll l, ll r, ll id, ll v) {
if (l > y || r < x) return;
if (x <= l && r <= y) {
tree[id].deladd = (tree[id].deladd * v) % mo;
tree[id].delx = (tree[id].delx * v) % mo;
tree[id].maxx = (tree[id].maxx * v) % mo;
return;
}
push_down(id, l, r);
ll mid = (l + r) >> 1;
updatax(l, mid, L(id), v);
updatax(mid + 1, r, R(id), v);
tree[id].maxx = (tree[L(id)].maxx + tree[R(id)].maxx) % mo;
return;
}

void updataadd(ll l, ll r, ll id, ll v) {
if (l > y || r < x) return;
if (x <= l && r <= y) {
tree[id].deladd = (tree[id].deladd + v) % mo;
tree[id].maxx = (tree[id].maxx + (r - l + 1) * v) % mo;
return;
}
push_down(id, l, r);
ll mid = (l + r) >> 1;
updataadd(l, mid, L(id), v);
updataadd(mid + 1, r, R(id), v);
tree[id].maxx = (tree[L(id)].maxx + tree[R(id)].maxx) % mo;
return;
}

ll findit(int l, int r, int id) {
if (l > y || r < x) return 0;
if (x <= l && r <= y) {
return tree[id].maxx % mo;
}
push_down(id, l, r);
ll mid = (l + r) >> 1;
ll t1 = findit(l, mid, L(id));
ll t2 = findit(mid + 1, r, R(id));
return (t1 + t2) % mo;
}

平衡树

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
inline bool relation(int pos) {
return pos == rc(tree[pos].fa);
}

inline void maintain(int pos) {
tree[pos].siz = tree[lc(pos)].siz + tree[rc(pos)].siz + tree[pos].wit;
}

inline void ins(int x, int y, int z) {
tree[x].son[z] = y;
tree[y].fa = x;
}

inline void rotate(int pos) {
int f = father(pos);
bool flag = relation(pos);
ins(father(f), pos, relation(f));
ins(f, tree[pos].son[flag^1], flag);
ins(pos, f, flag^1);
maintain(f);
maintain(pos);
if (!father(pos)) root = pos;
}

void splay(int pos, int tar = 0) {
while (tree[pos].fa != tar) {
if (tree[father(pos)].fa != tar) {
if (relation(pos) == relation(father(pos))) rotate(father(pos));
else rotate(pos);
}
rotate(pos);
}
}

int pre(int v) {
int pos = root, ans = 0;
while (pos) {
if (tree[pos].v >= v) pos = lc(pos);
else {
ans = pos;
pos = rc(pos);
}
}
splay(ans);
return root;
}

int succ(int v) {
int ans = 0, pos = root;
while (pos) {
if (tree[pos].v <= v) pos = rc(pos);
else {
ans = pos;
pos = lc(pos);
}
}
splay(ans);
return root;
}

int find(int v) {
int pos = root;
while (pos && tree[pos].v != v) {
if (v < tree[pos].v) pos = lc(pos);
else pos = rc(pos);
}
if (pos) {
splay(pos);
//return root;
}
return root;
}

void del(int v) {
int pos = find(v);
if (tree[pos].wit > 1) {
--tree[pos].siz;
--tree[pos].wit;
return;
}
int y = succ(v);
int x = pre(v);
splay(y, x);
//lc(y) = 0;
tree[y].son[0] = 0;
--tree[y].siz;
--tree[x].siz;
//dfs(root);
}

int insert(int v) {
int pos = root, lt = 0;
while (pos && tree[pos].v != v) {
++tree[pos].siz;
lt = pos;
if (v < tree[pos].v) pos = lc(pos);
else pos = rc(pos);
}
if (pos) {
++tree[pos].siz;
++tree[pos].wit;
}
else {
pos = ++len;
tree[pos].v = v;
tree[pos].siz = tree[pos].wit = 1;
lc(pos) = rc(pos) = 0;
father(pos) = lt;
tree[lt].son[v > tree[lt].v] = pos;
}
splay(pos);
return root;
}

int rank(int v) {
int pos = find(v);
if (!pos) {
pos = insert(v);
int ans = tree[lc(pos)].siz;
del(v);
return ans;
}
return tree[lc(pos)].siz;
}

int kth(int k) {
int pos = root;
int sz = tree[lc(pos)].siz;
while (k < sz || k >= sz + tree[pos].wit) {
if (k < sz) pos = lc(pos);
else {
k -= sz + tree[pos].wit;
pos = rc(pos);
}
sz = tree[lc(pos)].siz;
}
splay(pos);
return tree[pos].v;
}
////区间反转,find要加pushdown
void rever(int x, int y) {
int xx = find(root, x);
int yy = find(root, y + 2);
splay(xx);
splay(yy, xx);
tree[lc(yy)].rev ^= 1;
}

inline void pushdown(int pos) {
if (tree[pos].rev) {
tree[pos].rev = 0;
std::swap(lc(pos), rc(pos));
if (lc(pos)) tree[lc(pos)].rev ^= 1;
if (rc(pos)) tree[rc(pos)].rev ^= 1;
}
}

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
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
struct treap_node{
int fix, val, tim, size, weight, id;
int l, r;
}treap[sid + 100];

inline int left_size(int p) {
return treap[p].l ? treap[treap[p].l].size : 0;
}
inline int right_size(int p) {
return treap[p].r ? treap[treap[p].r].size : 0;
}

struct hash_string{
char ch[15];
int len;
}hash[sid + 100];

int bkdr_hash() {
int temp = 0;
int seed = 131;
int i = 1;
int k = strlen(str + 1);
while (i <= k) {
temp = temp * seed + str[i];
++i;
temp %= sid;
}
return temp % sid;
}

int find() {
int temp = bkdr_hash();
while (strlen(hash[temp].ch + 1) && strcmp(hash[temp].ch + 1, str + 1)) {
temp += step;
if (temp > sid) temp -= sid;
}
return temp;
}

void treap_left_rotate(int &a) {
int b = treap[a].r;
treap[a].r = treap[b].l;
treap[b].l = a;
a = b;
b = treap[a].l;
treap[b].size = left_size(b) + right_size(b) + treap[b].weight;
treap[a].size = left_size(a) + right_size(a) + treap[a].weight;
}

void treap_right_rotate(int &a) {
int b = treap[a].l;
treap[a].l = treap[b].r;
treap[b].r = a;
a = b;
b = treap[a].r;
treap[b].size = left_size(b) + right_size(b) + treap[b].weight;
treap[a].size = left_size(a) + right_size(a) + treap[a].weight;
}

void treap_insert(int &p, int val, int tim, int id) {

if (!p) {
p = ++tot;
treap[p].val = val;
treap[p].fix = rand() * rand() % 19260817;
treap[p].tim = tim;
treap[p].id = id;
treap[p].weight = 1;
treap[p].size = 1;
mark[id] = val;
taim[id] = tim;
return;
}
++treap[p].size;
if (val > treap[p].val) {
treap_insert(treap[p].l, val, tim, id);
if (treap[treap[p].l].fix < treap[p].fix)
treap_right_rotate(p);
}
else if (val < treap[p].val) {
treap_insert(treap[p].r, val, tim, id);
if (treap[treap[p].r].fix < treap[p].fix)
treap_left_rotate(p);
}
else {
if (tim < treap[p].tim) {
treap_insert(treap[p].l, val, tim, id);
if (treap[treap[p].l].fix < treap[p].fix)
treap_right_rotate(p);
}
else {
treap_insert(treap[p].r, val, tim, id);
if (treap[treap[p].r].fix < treap[p].fix)
treap_left_rotate(p);
}
}
}

void treap_delete(int &p, int id) {
if (!p) return;
if (treap[p].id == id) {
if ((!treap[p].r) || (!treap[p].l)) {
if (treap[p].l) p = treap[p].l;
else if (treap[p].r) p = treap[p].r;
else p = 0;
return;
}
else {
if (treap[treap[p].l].fix < treap[treap[p].r].fix) {
treap_right_rotate(p);
treap_delete(treap[p].r, id);
--treap[p].size;
}
else {
treap_left_rotate(p);
treap_delete(treap[p].l, id);
--treap[p].size;
}
}
}
else if (mark[id] > treap[p].val) {
treap_delete(treap[p].l, id);
--treap[p].size;
}
else if (mark[id] < treap[p].val){
treap_delete(treap[p].r, id);
--treap[p].size;
}
else {
if (taim[id] < treap[p].tim) {
treap_delete(treap[p].l, id);
--treap[p].size;
}
else {
treap_delete(treap[p].r, id);
--treap[p].size;
}
}
}

int treap_rank(int p, int id, int cur) {
if (!p) return 0;
if (treap[p].id == id)
return left_size(p) + 1 + cur;
else if (mark[id] > treap[p].val)
return treap_rank(treap[p].l, id, cur);
else if (mark[id] < treap[p].val)
return treap_rank(treap[p].r, id, cur + left_size(p) + treap[p].weight);
else {
if (taim[id] < treap[p].tim)
return treap_rank(treap[p].l, id, cur);
else
return treap_rank(treap[p].r, id, cur + left_size(p) + treap[p].weight);
}
}

int treap_kth(int p, int k) {
if (k < left_size(p) + 1) return treap_kth(treap[p].l, k);
else if (k > left_size(p) + treap[p].weight)
return treap_kth(treap[p].r, k - (left_size(p) + treap[p].weight));
else return treap[p].id;
}
带指针
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
struct treap{
int fix;
int val;
int cnt;
treap *l, *r;
};
treap *root = NULL;

void left_rotate(treap* &a) {
treap *b = a -> r;
a -> r = b -> l;
b -> l = a;
a = b;
}

void right_rotate(treap* &a) {
treap *b = a -> l;
a -> l = b -> r;
b -> r = a;
a = b;
}

void treap_insert(treap* &p, int val) {
if (p == NULL) {
p = new treap;
p -> val = val;
p -> fix = rand();
p -> cnt = 1;
p -> l = p -> r = NULL;
return;
}
if (val == p -> val) p -> cnt += 1;
else if (val < p -> val) {
treap_insert(p -> l, val);
if (p -> l -> fix < p -> fix)
right_rotate(p);
}
else if (val > p -> val) {
treap_insert(p -> r, val);
if (p -> r -> fix < p -> fix)
left_rotate(p);
}
}

inline int treap_max(treap *p) {
while (p -> r)
p = p -> r;
return p -> val;
}

inline int treap_min(treap *p) {
while (p -> l)
p = p -> l;
return p -> val;
}

void treap_delete(treap *&p, int val) {
if (!p) return;
if (val == p -> val) {
p->cnt -= 1;
if (!p -> cnt) {
if (!p -> l || !p -> r) {
treap *t = p;
if (!p -> l) p = p -> r;
else p = p -> l;
delete t;
}
else {
if (p -> l -> fix < p -> r -> fix) {
right_rotate(p);
treap_delete(p -> r, val);
}
else {
left_rotate(p);
treap_delete(p -> l, val);
}
}
}
}
else if (val < p -> val)
treap_delete(p -> l, val);
else
treap_delete(p -> r, val);
}

基础

倍增

RMQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[120][10];//max
int b[120][10];//min
void ST() {
for (int j = 1; (1 << j) <= n; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
a[i][j] = max(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
b[i][j] = min(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
}
}
void rangemax(int x,int y) {
int k = 0;
while ((1 << (k + 1)) <= y - x + 1) ++k;
printf("%d\n", max(a[x][k], a[y - (1 << k) + 1][k]));
}
void rangemin(int x,int y) {
int k = 0;
while ((1 << (k + 1)) <= y - x + 1) ++k;
printf("%d\n", min(b[x][k], b[y - (1 << k) + 1][k]));
}

快速幂

1
2
3
4
5
6
7
8
9
long long fastpower(int x, int y) {
long long t = 1;
while (y) {
if (y & 1) t = t * x % mod;
x = x * x % mod;
y = y >> 1;
}
return t;
}

归并排序

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
void work(int l, int r) {
int i, j, mid, temp;
if (l + 1 < r) {
mid = (l + r) / 2;
work(l, mid - 1);
work(mid, r);
temp = l;
for (i = l, j = mid; (i <= mid - 1) && (j <= r); ) {
if (a[i] > a[j]) {
c[temp++] = a[j++];
ans += mid - i;
}
else c[temp++] = a[i++];
}
if (j <= r) {
for (; j <= r; j++) c[temp++] = a[j];
}
else {
for (; i <= mid - 1; i++) c[temp++] = a[i];
}
for (int i = l; i <= r; i++) a[i] = c[i];
}
else {
if (l + 1 == r) {
if (a[l] > a[r]) {
int tt = a[r];
a[r] = a[l];
a[l] = tt;
ans++;
}
}
}
}