st表
模板题:洛谷 P3865
代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int f[100005][20];
int main()
{
int n,m;
int x,y;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&f[i][0]);
}
for(int j=1;j<=21;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]);
}
}
while(m--)
{
scanf("%d %d",&x,&y);
int cc=log2(y-x+1);
printf("%d\n",max(f[x][cc],f[y-(1<<cc)+1][cc]));
}
return 0;
}
树上倍增求LCA
模板题:洛谷 P3379
代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int head[1000005],dep[500005];
int f[500005][21],max0=20,cnt=1;
struct node
{
int to,next,w;
}q[1000010];
void add(int x,int y)
{
q[cnt].to=y;
q[cnt].next=head[x];
head[x]=cnt++;
}
void dfs(int u)
{
for(int i=1;i<=max0;i++)
{
if(f[u][i-1])
{f[u][i]=f[f[u][i-1]][i-1];} //在dfs(x)之前,x的父辈们的fa数组都已经计算完毕,所以可以用来计算x
else
{break;}//如果x已经没有第2^(i-1)个父亲了,那么也不会有更远的父亲,直接break
}
for(int i=head[u];i!=-1;i=q[i].next)
{
int v=q[i].to;
if(v!=f[u][0]) //如果v不是x的父亲就是x的儿子
{
f[v][0]=u; //记录儿子的第一个父亲是x
dep[v]=dep[u]+1; //处理深度
dfs(v);
}
}
}
int LCA(int u,int v)
{
if(dep[u]<dep[v]){swap(u,v);}//我们默认u的深度一开始大于v,那么如果u的深度小就交换u和v
int delta=dep[u]-dep[v];//计算深度差
for(int x=0;x<=max0;x++)//此循环用于提到相同的深度
{
if((1<<x)&delta)
{u=f[u][x];}
}
if(u==v){return u;}
for(int x=max0;x>=0;x--) ///注意!此处循环必须是从大到小!因为我们应该越提越“精确”
{
if(f[u][x]!=f[v][x])
{
u=f[u][x];
v=f[v][x];
}
}
return f[u][0];//此时u、v的第一个父亲就是LCA
}
int main()
{
memset(head,-1,sizeof(head));
int n,m,s,x,y;
scanf("%d %d %d",&n,&m,&s);
for(int i=1;i<=n-1;i++)
{scanf("%d %d",&x,&y);
add(x,y);add(y,x);}//链式前向星存储这颗树
dfs(s);//跑一遍dfs获得这颗树的信息,比如节点的父亲节点和深度
while(m--)
{
scanf("%d %d",&x,&y);
printf("%d\n",LCA(x,y));
}
return 0;
}
待更新~