倍增
ST表
主要用来解决RMQ(区间最大/最小值查询)问题。应用倍增思想,可以实现O(nlogn)预处理、O(1)查询。
预处理ST表
f[i][j]表示以第i个数为起点,长度为2^j的区间中的最大值，即f[i][j] = max(f[i][j -1], f[i+2^(j-1)][j-1])处理询问
对查询区间[l,r]做分割、拼凑。区间长度的指数k=log2(r-l+1)，并且区间[l,r]必可以由两个长度为2^k的区间重叠取最值，即
max(f[l][k],f[r-2^k+1][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
using namespace std;
int n,m;
// f[i][j]表示以第i个数为起点,长度为2^j的区间中的最大值
int f[100010][100];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>f[i][0];
// 预处理ST表
for(int j=1;j<=30;j++)
{
for(int i=1;i+(1<<j)-1<=n;i++)
{
f[i][j]=max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}
}
// 处理询问
for(int i=1,l,r;i<=m;i++)
{
cin>>l>>r;
int k=log2(r-l+1);
cout<<max(f[l][k], f[r-(1<<k)+1][k])<<endl;
}
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
using namespace std;
struct Edge
{
int from, to, next;
}edge[1000010];
int head[1000010], cnt=0;
void add(int x, int y)
{
edge[cnt].from=x;
edge[cnt].to=y;
edge[cnt].next=head[x];
head[x]=cnt++;
}
int n,m,s,a,b;
// dep存节点深度，fa[u][i]存从u点向上跳2^i次的节点(i从0开始计算)
int dep[500010], fa[500010][20];
void dfs(int u, int father)
{
dep[u]=dep[father]+1;
fa[u][0]=father;
for(int i=1;i<=19;i++)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=head[u];i!=-1;i=edge[i].next)
{
if(edge[i].to!=father) dfs(edge[i].to, u);
}
}
int lca(int u, int v)
{
// 第一阶段 将u、v跳到同一层
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--)
{
if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
}
if(u==v) return u;
// 第二阶段 将u、v跳到lca的下一层
for(int i=19;i>=0;i--)
{
if(fa[u][i]!=fa[v][i])
{
u=fa[u][i];
v=fa[v][i];
}
}
return fa[u][0];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin>>n>>m>>s;
for(int i=1;i<=n;i++) head[i]=-1;
for(int i=1;i<n;i++)
{
cin>>a>>b;
add(a,b), add(b,a);
}
dfs(s, 0);
while(m--)
{
cin>>a>>b;
cout<<lca(a,b)<<endl;
}
}
查询树上两点间路径上边权的最小值
在原本最近公共祖先的基础上加以minn数组存储最小值即可，完整代码见下：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// ...
int n,m,s,a,b,w;
// dep存节点深度，fa[u][i]存从u点向上跳2^i次的节点(i从0开始计算)
int dep[500010], fa[500010][20];
int minn[500010][20];
void dfs(int u, int father)
{
dep[u]=dep[father]+1;
fa[u][0]=father;
for(int i=1;i<=19;i++)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
minn[u][i]=min(minn[fa[u][i-1]][i-1], minn[u][i-1]);
}
for(int i=head[u];i!=-1;i=edge[i].next)
{
if(edge[i].to!=father)
{
minn[edge[i].to][0]=edge[i].weight;
dfs(edge[i].to, u);
}
}
}
int lca(int u, int v)
{
int ans=0x7f7f7f7f;
// 第一阶段 将u、v跳到同一层
if(dep[u]<dep[v]) swap(u,v);
for(int i=19;i>=0;i--)
{
if(dep[fa[u][i]]>=dep[v]) ans=min(ans, minn[u][i]) ,u=fa[u][i];
}
if(u==v) return ans;
// 第二阶段 将u、v跳到lca的下一层
for(int i=19;i>=0;i--)
{
if(fa[u][i]!=fa[v][i])
{
// 先赋完值再往上跳
ans=min(ans, min(minn[u][i], minn[v][i]));
u=fa[u][i];
v=fa[v][i];
}
}
ans=min(ans, min(minn[u][0], minn[v][0]));
return ans;
}
signed main()
{
// ...
for(int i=1;i<n;i++)
{
cin>>a>>b>>w;
add(a,b,w), add(b,a,w);
}
// ...
}
可用此数据测试1
2
3
4
5
6
7
8
9
105 5 4
3 1 1
2 4 6
5 1 3
1 4 5
2 4
3 2
3 5
1 2
4 5
NOIP 2013 T3 货车运输
本题先使用Kruskal算法建立最大生成树，随后使用上方的方法查询两点路径最小值即可得到答案。
注意，本题需要对所有没经过的点跑一遍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
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
using namespace std;
// union-find
int ufa[1000010];
int find(int x)
{
if(ufa[x]==x) return x;
else return ufa[x]=find(ufa[x]);
}
void merge(int a, int b)
{
ufa[find(a)]=find(b);
}
struct Node
{
int from, to, weight;
}node[1000010];
bool cmp(Node a, Node b)
{
return a.weight>b.weight;
}
bool vis[1000010];
bool dfs_vis[1000010];
struct Edge
{
int to, next, weight;
}edge[1000010];
int head[1000010], cnt=0;
void add(int x, int y, int z)
{
edge[cnt].to=y;
edge[cnt].weight=z;
edge[cnt].next=head[x];
head[x]=cnt++;
}
// dep存节点深度，fa[u][i]存从u点向上跳2^i次的节点(i从0开始计算)
int dep[500010], fa[500010][30];
int minn[500010][30];
void dfs(int u, int father)
{
dfs_vis[u]=true;
dep[u]=dep[father]+1;
fa[u][0]=father;
for(int i=1;i<=29;i++)
{
fa[u][i]=fa[fa[u][i-1]][i-1];
minn[u][i]=min(minn[fa[u][i-1]][i-1], minn[u][i-1]);
}
for(int i=head[u];i!=-1;i=edge[i].next)
{
if(edge[i].to!=father)
{
minn[edge[i].to][0]=edge[i].weight;
dfs(edge[i].to, u);
}
}
}
int lca(int u, int v)
{
int ans=0x7f7f7f7f;
// 第一阶段 将u、v跳到同一层
if(dep[u]<dep[v]) swap(u,v);
for(int i=29;i>=0;i--)
{
if(dep[fa[u][i]]>=dep[v]) ans=min(ans, minn[u][i]) ,u=fa[u][i];
}
if(u==v) return ans;
// 第二阶段 将u、v跳到lca的下一层
for(int i=29;i>=0;i--)
{
if(fa[u][i]!=fa[v][i])
{
// 先赋完值再往上跳
ans=min(ans, min(minn[u][i], minn[v][i]));
u=fa[u][i];
v=fa[v][i];
}
}
ans=min(ans, min(minn[u][0], minn[v][0]));
return ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) head[i]=-1, ufa[i]=i;
for(int i=1;i<=m;i++)
{
cin>>node[i].from>>node[i].to>>node[i].weight;
}
sort(node+1, node+1+m, cmp);
for(int i=1;i<=m;i++)
{
if(find(node[i].from)!=find(node[i].to))
{
add(node[i].from, node[i].to, node[i].weight);
add(node[i].to, node[i].from, node[i].weight);
merge(node[i].from, node[i].to);
vis[node[i].from]=true;
vis[node[i].to]=true;
}
}
for(int i=1;i<=n;i++){
if(dfs_vis[i]==false){
dfs(i,0);
}
}
int q;
cin>>q;
for(int i=1,a,b;i<=q;i++)
{
cin>>a>>b;
if(find(a)!=find(b)) cout<<"-1"<<endl;
else cout<<lca(a,b)<<endl;
}
}