OI - Templates

咕~

一些引用

  • 数据结构 - 普通平衡树/伸展树一节的简介来自百度百科
  • 数据结构 - 分块一节的简介来自 Siyuan’s Blog.
  • 数据结构 - 莫队一节的简介部分来自 WAMonster’s Blog (有删改)
  • 数据结构 - 块状链表一节的简介部分来自过往记忆的博客 (有删改)
  • 数据结构 - 树链剖分(重链剖分)一节的简介部分来自Sshwy’s Blog (有删改)

数据结构

ST List

ST表是一种可以用于静态区间最值$\mathcal O(1)$查询的数据结构, 主要利用了倍增的思想.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int MAXM = 20 + 7;
const int MAXN = 1e6 + 1;
int ST[MAXN][MAXM];
inline void init(){
FOR(j, 1, MAXM, 1){
for(int i = 1; i + (1 << j) -1 <= n; i++){
ST[i][j] = std::max(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
}
}
}
inline int Query(int l,int r){
int k = (int)(std::log(r - l + 1) / std::log(2));
return std::max(ST[l][k], ST[r - (1 << k) + 1][k]);
}

// 调用接口:
//1. 查询区间[l,r]内的权值最大值.
int ans = Query(l, r);

树状数组(BIT)

树状数组是一种可以支持单点修改, 前缀/单点查询的数据结构, 经过差分可以支持区间修改.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define lowbit(x) x&(-x)

struct BIT{
int Tree[MAXN];
inline void Modify(int x,int val) {
while(x <= n) {Tree[x] += val; x += lowbit(x);}
}
inline int Query(int x) {
int ans = 0;
while(x) {ans += Tree[x]; x -= lowbit(x);}
return ans;
}
}T;

//调用接口:
//1. 单点修改, 将位置x的数的权值加上val:
T.Modify(x, val);
//2. 前缀查询, 查询前x个数的和
int ans = T.Query(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
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
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)|1
const int MAXN = 1e5 + 10;
struct SegMentTree{
long long tag,sum,add;
}Tree[MAXN << 2];
inline void pushUp(int k){
Tree[k].sum = Tree[LeftChild(k)].sum + Tree[RightChild(k)].sum;
if(Tree[k].sum >= Mod) Tree[k].sum -= Mod;
}
inline void pushDown(int k,int x){
Tree[LeftChild(k)].sum = (Tree[LeftChild(k)].sum * Tree[k].tag + Tree[k].add * ((x+1) >> 1)) % Mod;
Tree[RightChild(k)].sum = (Tree[RightChild(k)].sum * Tree[k].tag + Tree[k].add * (x >> 1))% Mod;
Tree[LeftChild(k)].tag = Tree[LeftChild(k)].tag * Tree[k].tag % Mod;
Tree[RightChild(k)].tag = Tree[RightChild(k)].tag * Tree[k].tag % Mod;
Tree[LeftChild(k)].add = (Tree[LeftChild(k)].add * Tree[k].tag + Tree[k].add) % Mod;
Tree[RightChild(k)].add = (Tree[RightChild(k)].add * Tree[k].tag + Tree[k].add) % Mod;
Tree[k].tag = 1;
Tree[k].add = 0;
}
inline void Build(int k, int l, int r){
Tree[k].tag = 1;
if(l == r){
Tree[k].sum = a[l];
return;
}
int mid = (l + r) >> 1;
Build(LeftChild(k),l,mid);
Build(RightChild(k),mid+1,r);
pushUp(k);
}
inline void UpdateMul(int x, int y, int k, int l, int r, long long val){
if(x <= l && r <= y){
Tree[k].tag = Tree[k].tag * val % Mod;
Tree[k].add = Tree[k].add * val % Mod;
Tree[k].sum = Tree[k].sum * val % Mod;
return;
}
pushDown(k,r-l+1);
int mid = (l + r) >> 1;
if(x <= mid) UpdateMul(LeftChild(k),l,mid,val);
if(mid < y) UpdateMul(RightChild(k),mid+1,r,val);
pushUp(k);
}
inline void UpdateAdd(int x, int y, int k, int l, int r, long long val){
if(x <= l && r <= y){
Tree[k].add += val;
if(Tree[k].add >= Mod) Tree[k].add -= Mod;
Tree[k].sum = (Tree[k].sum + (r - l + 1) * val) % Mod;
return;
}
pushDown(k,r-l+1);
int mid = (l + r) >> 1;
if(x <= mid) UpdateAdd(LeftChild(k),l,mid,val);
if(mid < y) UpdateAdd(RightChild(k),mid+1,r,val);
pushUp(k);
}
inline long long Query(int x, int y, int k, int l, int r){
if(x <= l && r <= y) return Tree[k].sum;
pushDown(k,r-l+1);
int mid = (l + r) >> 1;
long long ans = 0;
if(x <= mid) ans += Query(LeftChild(k),l,mid);
if(mid < y) ans += Query(RightChild(k),mid+1,r);
if(ans >= Mod) ans -= Mod;
pushUp(k);
return ans;
}
//调用接口:
//1. 对区间[l,r]内的数的权值都加上val
UpdateAdd(l, r, 1, 1, n, val);
//2. 对区间[l,r]内的数的权值都乘上val
UpdateMul(l, r, 1, 1, n, val);
//3. 查询区间[l,r]内的数的权值和, 对Mod取模
long long ans = Query(l, r, 1, 1, n);

二叉堆

具体可以看我之前的一篇屑文章, Link.

1
2
3
4
5
6
7
8
9
10
11
12
13
//大根堆
std::priority_queue<int> Q;
//小根堆
std::priority_queue<int, std::vector<int>, std::greater<int> > Q;
//调用接口:
//1. 向堆内插入一个元素x
Q.push(x)
//2. 删除堆顶
Q.pop()
//3. 获取堆顶
int TOP = Q.top()
//4. 获取堆是否为空
bool isempty = Q.empty()

并查集/带权并查集

并查集可以维护图的连通性, 可以通过路径压缩和按秩合并两种方式进行优化.

1
2
3
4
5
6
7
8
9
int UFS[MAXN];
inline int Find(int x) {
if(x == UFS[x]) return x;
return UFS[x] = Find(UFS[x]);
}
inline void unionx(int x, int y) {
int findx = Find(x), findy = Find(y);
if(findx != findy) UFS[findy] = findx;
}

可持久化线段树

可持久化线段树, 又称主席树, 可以在普通线段树的基础上支持回滚到某一历史版本.

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
const int MAXM = 2e5 + 10;
const int inf = INT_MAX;
struct SegMent{
int lch,rch;
int sum;
}Tree[MAXM * 20];
int n,m,cnt,t,v[MAXM],disc[MAXM],history[MAXM];
inline void Build(int &k,int l,int r){
k = ++cnt;
Tree[k].sum = 0;
if(l == r) return;
int mid = (l + r) >> 1;
Build(Tree[k].lch,l,mid);
Build(Tree[k].rch,mid + 1,r);
}
inline int Update(int k,int l,int r,int place,int val){
int u = ++cnt;
Tree[u] = Tree[k];
if(l == r){
Tree[u].sum += val; return u;
}
int mid = (l + r) >> 1;
if(place <= mid) Tree[u].lch = Update(Tree[k].lch,l,mid,place,val);
else Tree[u].rch = Update(Tree[k].rch,mid + 1,r,place,val);
Tree[u].sum = Tree[Tree[u].lch].sum + Tree[Tree[u].rch].sum;
return u;
}
inline int Query(int p,int q,int l,int r,int k){
if(l == r) return l;
int mid = (l + r) >> 1;
int L_tot = Tree[Tree[p].lch].sum - Tree[Tree[q].lch].sum;
if(k <= L_tot) return Query(Tree[p].lch,Tree[q].lch,l,mid,k);
else return Query(Tree[p].rch,Tree[q].rch,mid + 1,r,k - L_tot);
}
inline void init() {
scanf("%d%d",&n,&m);
FOR(i, 1, n, 1) {
scanf("%d",&v[i]);
disc[++t] = v[i];
}
std::sort(disc+1,disc+t+1);
t = std::unique(disc+1,disc+t+1) - disc - 1;
Build(history[0],1,t);
FOR(i,1,n,1){
int now = std::lower_bound(disc+1,disc+t+1,v[i]) - disc;
history[i] = Update(history[i - 1],1,t,now,1);
}
}
//调用接口
//1. 初始化
init();
//2. 查询区间[l, r]内第k小的数.
int ans = Query(history[r], history[l - 1], 1, t, k);

普通平衡树(Treap)

树堆,在数据结构中也称Treap,是指有一个随机附加域满足堆的性质的二叉搜索树,其结构相当于以随机数据插入的二叉搜索树。

其基本操作的期望时间复杂度为$\mathcal O(\log n)$。相对于其他的平衡二叉搜索树,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
const int MAXN = 1e6 + 19;
const int INF = INT_MAX;
struct treap{
int cnt,size,val,prio;
int ch[2];
}Treap[MAXN];
int tot,root,n;
inline int New(int v){
Treap[++tot].val = v;
Treap[tot].prio = std::rand();
Treap[tot].size = Treap[tot].cnt = 1;
return tot;
}
inline void pushUp(int x){
Treap[x].size = Treap[Treap[x].ch[0]].size + Treap[Treap[x].ch[1]].size + Treap[x].cnt;
}
inline void Build(){
root = New(-INF);
Treap[root].ch[1] = New(INF);
pushUp(root);
}
inline void Rotate(int &x,int d){
int tmp = Treap[x].ch[d ^ 1];
Treap[x].ch[d^1] = Treap[tmp].ch[d];
Treap[tmp].ch[d] = x; x = tmp;
pushUp(Treap[x].ch[d]); pushUp(x);
}
inline void Insert(int &x,int v){
if(!x){x = New(v); return;}
if(v == Treap[x].val) Treap[x].cnt++;
else{
int t = (v < Treap[x].val) ? 0 : 1;
Insert(Treap[x].ch[t],v);
if(Treap[x].prio < Treap[Treap[x].ch[t]].prio) Rotate(x,t ^ 1);
}
pushUp(x);
}
inline void Remove(int &x,int v){
if(!x) return;
if(v == Treap[x].val){
if(Treap[x].cnt > 1){Treap[x].cnt--; pushUp(x); return;}
if(Treap[x].ch[0] || Treap[x].ch[1]){
if(!Treap[x].ch[1] || Treap[Treap[x].ch[0]].prio > Treap[Treap[x].ch[1]].prio){
Rotate(x,1), Remove(Treap[x].ch[1],v);
}
else Rotate(x,0), Remove(Treap[x].ch[0],v);
pushUp(x);
}
else x = 0;
return;
}
(v < Treap[x].val) ? Remove(Treap[x].ch[0],v) : Remove(Treap[x].ch[1],v);
pushUp(x);
}
inline int Rank(int x,int v){
if(!x) return 0;
if(v == Treap[x].val) return Treap[Treap[x].ch[0]].size + 1;
else if(v < Treap[x].val) return Rank(Treap[x].ch[0],v);
else return Treap[Treap[x].ch[0]].size + Treap[x].cnt + Rank(Treap[x].ch[1],v);
}
inline int Value(int x,int rank){
if(!x) return INF;
if(rank <= Treap[Treap[x].ch[0]].size) return Value(Treap[x].ch[0],rank);
else if(rank <= Treap[Treap[x].ch[0]].size + Treap[x].cnt) return Treap[x].val;
else return Value(Treap[x].ch[1],rank - Treap[Treap[x].ch[0]].size - Treap[x].cnt);
}
inline int PREC(int v){
int x = root,pre;
while(x){
if(Treap[x].val < v) pre = Treap[x].val,x = Treap[x].ch[1];
else x = Treap[x].ch[0];
}
return pre;
}
inline int NEXT(int v){
int x = root,next;
while(x){
if(Treap[x].val > v) next = Treap[x].val, x = Treap[x].ch[0];
else x = Treap[x].ch[1];
}
return next;
}
//调用接口:
//1. 建树
Build();
//2. 插入一个权值为x的数
Insert(root, x);
//3. 删除一个权值为x的数, 如果有多个, 则只删除一个.
Remove(root, x);
//4. 查询数x的排名(比x小的数的个数+1)
int ans = Rank(root, x) + 1;
//5. 查询排名为x的数
int ans = Value(root, x + 1);
//6. 查询x的前趋
int ans = PREC(x);
//7. 查询x的后继
int ans = NEXT(x);

伸展树(Splay)

至于没有某fhq大爷发明的数据结构, 主要是我们机房的某些屑吹的太过了, 于是决定不挂了.

伸展树,也叫分裂树,是一种二叉排序树,它能在$\mathcal O(\log 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
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
const int MAXN = 2e5 + 10;
const int inf = INT_MAX;
struct Tree{
int ch[2], cnt, val, size, fa;
#define Lef(x, k) Splay[Splay[x].ch[0]].k
#define Rig(x, k) Splay[Splay[x].ch[1]].k
}Splay[MAXN];
int Node, root, n;
inline bool FIND(int x) {
return Splay[Splay[x].fa].ch[1] == x;
}
inline void pushUp(int x) {
Splay[x].size = Lef(x, size) + Rig(x, size) + Splay[x].cnt;
}
inline void Rotate(int x) {
int fx = Splay[x].fa, fy = Splay[fx].fa;
int chx = FIND(x), chy = Splay[x].ch[chx ^ 1];
Splay[fx].ch[chx] = chy; Splay[chy].fa = fx;
Splay[fy].ch[FIND(fx)] = x; Splay[x].fa = fy;
Splay[x].ch[chx ^ 1] = fx; Splay[fx].fa = x;
pushUp(fx); pushUp(x);
}
inline void splay(int x, int rt = 0) {
while(Splay[x].fa != rt) {
int fx = Splay[x].fa, fy = Splay[fx].fa;
if(fy != rt) {
if(FIND(x) == FIND(fx)) Rotate(fx);
else Rotate(x);
}
Rotate(x);
}
if(!rt) root = x;
}
inline void Insert(int x) {
int rt = root, p = 0;
while(rt && Splay[rt].val != x) {
p = rt;
rt = Splay[rt].ch[x > Splay[rt].val];
}
if(rt) Splay[rt].cnt++;
else {
rt = ++Node;
if(p) Splay[p].ch[x > Splay[p].val] = rt;
Splay[rt].ch[0] = Splay[rt].ch[1] = 0;
Splay[rt].fa = p; Splay[rt].val = x;
Splay[rt].cnt = Splay[rt].size = 1;
}
splay(rt);
}
inline void LowerX(int x) {
int rt = root;
while(Splay[rt].ch[x > Splay[rt].val] && x != Splay[rt].val)
rt = Splay[rt].ch[x > Splay[rt].val];
splay(rt);
}
inline int Queryrks(int x) {
LowerX(x);
return Lef(root, size);
}
inline int Querykth(int k) {
int rt = root;
while(true) {
if(Splay[rt].ch[0] && k <= Lef(rt, size))
rt = Splay[rt].ch[0];
else if(k > Lef(rt, size) + Splay[rt].cnt) {
k -= Lef(rt, size) + Splay[rt].cnt;
rt = Splay[rt].ch[1];
}
else return rt;
}
}
inline int Querypre(int x) {
LowerX(x);
if(Splay[root].val < x) return root;
int rt = Splay[root].ch[0];
while(Splay[rt].ch[1]) rt = Splay[rt].ch[1];
return rt;
}
inline int Querysuf(int x) {
LowerX(x);
if(Splay[root].val > x) return root;
int rt = Splay[root].ch[1];
while(Splay[rt].ch[0]) rt = Splay[rt].ch[0];
return rt;
}
inline void Remove(int x) {
int last = Querypre(x), next = Querysuf(x);
splay(last), splay(next, last);
int del = Splay[next].ch[0];
if(Splay[del].cnt > 1) {Splay[del].cnt--; splay(del);}
else Splay[next].ch[0] = 0;
}

//调用接口
//1. 插入一个权值为x的数
Insert(x);
//2. 删除一个权值为x的数, 如果有多个, 则只删除一个.
Remove(x);
//3. 查询第k大的数
int ans = Querykth(x);
//4. 查询数x的排名(比x小的数的个数+1)
int ans = Queryrks(x);
//5. 查询排名为x的数
int ans = Splay[Queryrks(x + 1)].val;
//6. 查询x的前趋
int ans = Querypre(x);
//7. 查询x的后继
int ans = Querysuf(x);

分块

分块算法,顾名思义是把一个长度为 $N$ 的序列分成 $M$ 块,每块的大小均为 $\frac NM$ 。

我们维护块内信息,使得块内信息的查询是 $\mathcal O(1)$ 的,而总的询问又可以看做是若干个块的询问的总和。

这里我们以LuoguP4145为例.

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
const int MAXN = 1e5 + 10;
int n, m, block, num, l[MAXN], r[MAXN], Belong[MAXN];
long long sum[MAXN], a[MAXN];
bool CSQRT[MAXN];
inline void Build() {
block = std::sqrt(n), num = (n / block) + (n % block != 0);
FOR(i, 1, n, 1) Belong[i] = (i - 1) / block + 1, sum[Belong[i]] += a[i];
FOR(i, 1, num, 1) l[i] = (i - 1) * block + 1, r[i] = i * block;
r[num] = n;
}
inline void BlockSqrt(int x) {
if (CSQRT[x] == true)
return;
sum[x] = 0, CSQRT[x] = true;
FOR(i, l[x], r[x], 1) sum[x] += (a[i] = std::sqrt(a[i])), CSQRT[x] &= (a[i] <= 1);
}
inline void UpdateSqr(int L, int R) {
if (Belong[L] == Belong[R]) {
for (int i = L; i <= R; ++i) sum[Belong[L]] -= a[i], sum[Belong[L]] += (a[i] = std::sqrt(a[i]));
} else {
for (int i = Belong[L] + 1; i <= Belong[R] - 1; ++i) BlockSqrt(i);
for (int i = L; i <= r[Belong[L]]; ++i)
sum[Belong[L]] -= a[i], sum[Belong[L]] += (a[i] = std::sqrt(a[i]));
for (int i = l[Belong[R]]; i <= R; ++i)
sum[Belong[R]] -= a[i], sum[Belong[R]] += (a[i] = std::sqrt(a[i]));
}
}
inline long long Query(int L, int R) {
long long ans = 0;
if (Belong[L] == Belong[R]) {
for (int i = L; i <= R; ++i) ans += a[i];
return ans;
}
for (int i = Belong[L] + 1; i <= Belong[R] - 1; ++i) ans += sum[i];
for (int i = L; i <= r[Belong[L]]; ++i) ans += a[i];
for (int i = l[Belong[R]]; i <= R; ++i) ans += a[i];
return ans;
}
//调用接口
//1. 初始化
Build();
//2. 对区间[l, r]开平方根
Update(l, r);
//3. 查询区间[l, r]内的数的和
long long ans = Query(l, r);

莫队

传说中能够解决一切区间问题的暴力优化算法.

莫队是由莫涛大神提出的,一种玄学毒瘤暴力骗分区间操作算法,它以简短的框架、简单易记的板子和优秀的复杂度闻名于世。

关于莫队, 还有几种变种. 比如(树上)带修莫队, 回滚莫队(当区间伸长时好处理, 缩短时不好处理时使用), 和著名毒瘤nzhtl1477大爷发明的二次离线莫队等等.

这里我们以最简单的莫队模板题, LuoguP1972为例.

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
const int MAXN = 1e6 + 1e4 + 10;
const int MAXB = 1e3 + 10;
struct Mo_Team{
int l,r,serial;
};
Mo_Team Q[MAXN];
int n,m,t,now,num,ans[MAXN];
int v[MAXN],cnt[MAXN],place[MAXN];
int L[MAXN],R[MAXN];
int cmp(Mo_Team a,Mo_Team b){
return (place[a.l] ^ place[b.l]) ? place[a.l] < place[b.l] : ((place[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
inline void init() {
t = std::sqrt(n);
num = std::ceil((double)n / t);
FOR(i,1,t,1){
L[i] = (i - 1) * t + 1;
R[i] = i * t;
}
FOR(i,1,num,1){
FOR(j,L[i],R[i],1) place[j] = i;
}
FOR(i,1,m,1){
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].serial = i;
}
std::sort(Q+1,Q+m+1,cmp);
}
inline void work() {
FOR(i,1,m,1){
int Ql = Q[i].l, Qr = Q[i].r;
while(l < Ql) now -= !--cnt[v[l++]];
while(l > Ql) now += !cnt[v[--l]]++;
while(r < Qr) now += !cnt[v[++r]]++;
while(r > Qr) now -= !--cnt[v[r--]];
ans[Q[i].serial] = now;
}
}
//调用接口
//1. 初始化 & 离线询问
init();
//2. 离线处理所有对区间[l, r]内有多少个不同的数的询问, 答案存储在ans数组中.
work();

块状链表

块状链表本身是一个链表,但是链表储存的并不是一般的数据,而是由这些数据组成的顺序表。

每一个块状链表的节点,可以被叫做一个块。块状链表通过使用可变的顺序表的长度和特殊的插入、删除方式,可以达到均摊每次操作复杂度$O(n\sqrt{n})$。

块状链表另一个特点是相对于普通链表来说节省内存,因为不用保存指向每一个数据节点的指针。

这里我们以LuoguP4008为例.

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
const int MAXN = 2e3 + 10;
const int MAXM = 2e7 + 10;
struct Node{
int next, size;
char str[MAXN << 1];
}Linked_List[MAXN << 2];
int pool[MAXN << 2], cnt, cpos;
char ans[MAXM];
inline int New() {return pool[cnt++];}
inline void Delete(int x) {pool[--cnt] = x;}
inline void init() {
FOR(i, 1, (MAXN << 2) - 1, 1) pool[i] = i;
cnt = 1; Linked_List[0].size = 0;
Linked_List[0].next = -1;
}
inline void NewBlock(int x, int y, int len, char *s) {
if(y != -1) {
Linked_List[y].next = Linked_List[x].next;
Linked_List[y].size = len;
memcpy(Linked_List[y].str, s, len);
}
Linked_List[x].next = y;
}
inline void Unionx(int x, int y) {
#define list Linked_List
memcpy(list[x].str + list[x].size, list[y].str, list[y].size);
list[x].size += list[y].size; list[x].next = list[y].next;
Delete(y);
#undef list
}
inline void Splitx(int x, int pos) {
if(x == -1 || pos == Linked_List[x].size) return ;
NewBlock(x, New(), Linked_List[x].size - pos, Linked_List[x].str + pos);
Linked_List[x].size = pos;
}
inline int CurSor(int &x) {
int now = 0;
while(now != -1 && x > Linked_List[now].size)
x -= Linked_List[now].size, now = Linked_List[now].next;
return now;
}
inline void Insert(int pos, int len, char *s) {
int now = CurSor(pos); Splitx(now, pos);
int tot = 0, st = now, Np;
while(tot + MAXN <= len) {
Np = New();
NewBlock(now, Np, MAXN, s + tot);
tot += MAXN; now = Np;
}
if(len - tot) Np = New(), NewBlock(now, Np, len - tot, s + tot);
if(Linked_List[now].size + Linked_List[Np].size < MAXN && Np != -1)
Unionx(now, Np), Np = Linked_List[now].next;
if(Linked_List[st].size + Linked_List[Linked_List[st].next].size < MAXN) {
if(Linked_List[st].next != -1) Unionx(st, Linked_List[st].next);
}
}
inline void Erase(int pos, int len) {
int now = CurSor(pos); Splitx(now, pos);
int nxt = Linked_List[now].next;
while(nxt != -1 && len > Linked_List[nxt].size)
len -= Linked_List[nxt].size, nxt = Linked_List[nxt].next;
Splitx(nxt, len); nxt = Linked_List[nxt].next;
for(int i = Linked_List[now].next; i != nxt; i = Linked_List[now].next)
Linked_List[now].next = Linked_List[i].next, Delete(i);
while(Linked_List[now].size + Linked_List[nxt].size < MAXN && nxt != -1)
Unionx(now, nxt), nxt = Linked_List[now].next;
}
inline void Print(int pos, int len) {
int curp = CurSor(pos);
int tot = Linked_List[curp].size - pos;
if(len < tot) tot = len;
memcpy(ans, Linked_List[curp].str + pos, tot);
int now = Linked_List[curp].next;
while(now != -1 && len >= tot + Linked_List[now].size) {
memcpy(ans + tot, Linked_List[now].str, Linked_List[now].size);
tot += Linked_List[now].size, now = Linked_List[now].next;
}
if(len - tot > 0 && now != -1)
memcpy(ans + tot, Linked_List[now].str, len - tot);
ans[len] = '\0'; printf("%s\n", ans);
}
inline char* GetString(int &len) {
scanf("%d", &len); char tmp[MAXN];
FOR(i, 0, len - 1, 1) {
tmp[i] = getchar();
if(tmp[i] < 32 || tmp[i] > 126) --i;
}
return tmp;
}
//调用接口
//1. 在位置cpos后面插入长度为len的读入的字符串
Insert(cpos, len, GetString(len));
//2. 删除cpos位置后的len个字符
Erase(cpos, len);
//3. 输出cpos后len个字符
Print(cpos, len);

树链剖分(重链剖分)

树链剖分可以将一棵树剖分成若干条链的形式, 使它组合成线性结构,然后用其他的数据结构维护树上路径/某个子树的信息。

重链剖分是指在剖分时, 定义一个节点的重儿子为子树大小最大的儿子, 其他节点为轻儿子. 所有的重节点构成的若干条链被称为重链.

容易发现, 所有的重链将整棵树完全剖分, 他们一定是链状结构, 不会连成一棵树.

重链在剖分时重边优先遍历,最后树的 DFN 序上,重链内的 DFN 序是连续的。按 DFN 排序后的序列即为剖分后的链.

这里我们以LuoguP2146为例

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
const int MAXN = 1e5 + 10;
const int MAXM = MAXN << 1;
#define int long long
struct Edge{int next, to;}Graph[MAXM];
struct SegMent{int l, r, sum, lazy;}SMT[MAXM << 1];
int head[MAXN], cnt, n, m, root, tot;
int fa[MAXN], depth[MAXN], top[MAXN], dfn[MAXN];
int son[MAXN], size[MAXN];
inline void Add_Edge(int from, int to) {
Graph[++cnt] = (Edge){head[from], to};
head[from] = cnt;
}
inline void DFS1(int u, int f, int dep) {
depth[u] = dep;
fa[u] = f; size[u] = 1;
for(int i = head[u]; i; i = Graph[i].next) {
if(Graph[i].to == f) continue;
DFS1(Graph[i].to, u, dep + 1);
size[u] += size[Graph[i].to];
if(size[Graph[i].to] > size[son[u]]) son[u] = Graph[i].to;
}
}
inline void DFS2(int u, int topf) {
dfn[u] = ++tot; top[u] = topf;
if(!son[u]) return ;
DFS2(son[u], topf);
for(int i = head[u]; i; i = Graph[i].next) {
if(!dfn[Graph[i].to]) DFS2(Graph[i].to, Graph[i].to);
}
}
inline void pushUp(int k) {
SMT[k].sum = SMT[LeftChild(k)].sum + SMT[RightChild(k)].sum;
}
inline void pushDown(int k) {
#define lazy(x) SMT[x].lazy
#define sum(x) SMT[x].sum
if(lazy(k) != -1) {
sum(LeftChild(k)) = (SMT[LeftChild(k)].r - SMT[LeftChild(k)].l + 1) * lazy(k);
sum(RightChild(k)) = (SMT[RightChild(k)].r - SMT[RightChild(k)].l + 1) * lazy(k);
lazy(LeftChild(k)) = lazy(k);
lazy(RightChild(k)) = lazy(k);
lazy(k) = -1;
}
}
inline void Build(int l, int r, int k) {
SMT[k].l = l; SMT[k].r = r;
SMT[k].sum = 0; SMT[k].lazy = -1;
if(l == r) return ;
int mid = (l + r) >> 1;
Build(l, mid, LeftChild(k));
Build(mid + 1, r, RightChild(k));
}
inline void Update(int l, int r, int v, int k) {
if(l <= SMT[k].l && SMT[k].r <= r) {
SMT[k].sum = (SMT[k].r - SMT[k].l + 1) * v;
SMT[k].lazy = v; return ;
}
pushDown(k);
int mid = (SMT[k].l + SMT[k].r) >> 1;
if(l <= mid) Update(l, r, v, LeftChild(k));
if(r > mid) Update(l, r, v, RightChild(k));
pushUp(k);
}
inline void Modify(int x, int y, int v) {
while(top[x] != top[y]) {
if(depth[top[x]] < depth[top[y]]) std::swap(x, y);
Update(dfn[top[x]], dfn[x], v, 1);
x = fa[top[x]];
}
if(depth[x] > depth[y]) std::swap(x, y);
Update(dfn[x], dfn[y], v, 1);
}
inline void init() {DFS1(1, 0, 1); DFS2(1, 1); Build(1, n, 1);}
//调用接口:
//1. 初始化
init();
//2. 把节点x到节点y节点路径上的值赋为x
Modify(x, y, x);
//3. 把以x为根节点的子树的权值赋为v
Update(dfn[x], dfn[x] + size[x] - 1, v, 1);

数论/数学

基础操作

此板块内的变量定义均遵从以下代码.

1
#define type_T long long

最大公约数/最小公倍数

我们采用欧几里得算法求出两个数的最大公约数/最小公倍数, 时间复杂度$\mathcal O(\log \max a,b)$

1
2
3
4
5
6
7
8
9
10
11
inline type_T gcd(type_T a, type_T b) {
return (!b) ? a : gcd(b, a % b);
}
inline type_T lcm(type_T a, type_T b) {
return a * b / gcd(a, b);
}
//调用接口
//1. 求两个数a,b的最大公约数
type_T ans = gcd(a, b);
//2. 求两个数a,b的最小公倍数
type_T ans = lcm(a, b);

快速幂算法

快速幂算法可以在$\mathcal O(\log b)$的时间内计算出$a^b \mod p$的值, 主要利用了分治的思想.

1
2
3
4
5
6
7
8
9
10
inline type_T quick_power(type_T a, type_T b, type_T p) {
type_T res = 1, base = a;
while(b) {
if(b & 1) res = 1ll * res * base % p;
b >>= 1; base = 1ll * base * base % p;
}
return res;
}
//调用接口
type_T ans = quick_power(a, b, p);

快速乘算法

快速乘算法利用了unsigned long long的自然溢出, 可以在$\mathcal O(1)$时间内解决两个long long型变量相乘并取模的问题.

1
2
3
4
5
6
7
8
#define type_U unsigned long long
inline type_T quick_multi(type_T a, type_T b, type_T p) {
type_T k = (long double) a / p * b;
type_T res = (type_U)a * b - (type_U)k * p;
return (res + p) % p;
}
//调用接口
type_T ans = quick_multi(a, b, p);

扩展欧几里得算法(exgcd)

求解形如$ax + by = c (a, b, c, x, y \in \Bbb Z)$的不定方程, 可以转化为形如$ax \equiv b \pmod{p}$的线性同余方程.

时间复杂度$\mathcal O(\log(\max a,b))$

1
2
3
4
5
6
inline type_T exgcd(type_T a, type_T b, type_T &x, type_T &y) {
if(!b) {x = 1, y = 0; return a;}
type_T d = exgcd(b, a % b, x, y);
type_T tmp = x; x = y, y = tmp - a / b * y;
return d;
}

乘法逆元

解决模意义下的除法问题.

费马小定理

1
2
3
//调用接口:
//求出x在模p意义下的乘法逆元
type_T inv = quick_power(x, p - 2, p);

线性预处理乘法逆元

1
2
3
4
//调用接口:
//线性处理出1~n所有自然数在模p意义下的乘法逆元
inv[1] = 1;
FORR(i, 2, n, 1) inv[i] = (p - p / i) * inv[p % i] % p;

应用举例

求出$\frac n2 \mod p$, $n \leq 10^{18}, p = 10^9 + 7$, $n$为正整数.

1
type_T ans = quick_multi(n, quick_power(2, p - 2, p), p);