P3379 【模板】最近公共祖先(LCA)

LCA(Lowest Common Ancestor)模板,注释写得很详细了 ~~(大佬请自动忽略我写的冗长的注释)~~

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,x,y,s,v,cnt,f[N][21],dep[N],head[N];//f[i][j]表示i的2^j祖先,也就是i向上跳2^j步的点。dep表示深度。
struct node
{
    int to,next;
}e[N<<1];//无向图开两倍大小
void add(int x,int y)//链式前向星存边
{
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void dfs(int u,int father)//预处理得到f数组,u表示当前搜索到的点,father表示u的父节点
{
    dep[u]=dep[father]+1;//u的父节点深度+1就是u的深度
    f[u][0]=father;//u向上跳2^0步(1步),为father点
    for(int i=1;i<=20;i++)//u与其祖先的距离最大不超过2^20
        f[u][i]=f[f[u][i-1]][i-1];//dp的思想:u向上跳2^i步相当于u向上跳2^(i-1)步,再向上跳2^(i-1)步
    for(int i=head[u];i!=-1;i=e[i].next)//遍历与u相连的点
    {
        v=e[i].to;
        if(v!=father)dfs(v,u);//如果当前遍历的点v不是father点,则可以向下继续搜索
    }
}
int lca(int x,int y)//求最近公共祖先(LCA)
{
    if(dep[x]<dep[y])swap(x,y);//保证x的深度大于等于y的深度
    for(int i=20;i>=0;i--)//依次尝试x向上跳2^logn,...2^1,2^0步(logn最大不超过20)
    {
        if(dep[f[x][i]]>=dep[y])x=f[x][i];//让x向上跳,直到与y同深度
        if(x==y)return x;//若x跳到与y同深度时与y重合,则说明x,y的最近公共祖先就是原来的y(也是现在的x)
    }
    for(int i=20;i>=0;i--)//依次尝试x,y向上跳2^logn,...2^1,2^0步(logn最大不超过20)
    {
        if(f[x][i]!=f[y][i])//若x,y同时向上跳2^i步后不重合,此时x,y可以同时向上跳
        {
            x=f[x][i];
            y=f[y][i];
        }
    }//结束循环时,必定有x与y的父节点相同,即答案为f[x][0]=f[y][0]
    return f[x][0];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n-1;i++)
    {
        cin>>x>>y;
        add(x,y);
        add(y,x);//无向树,反向也要加边
    }
    dfs(s,0);//从起点s开始搜索,设起点的父节点为0
    while(m--)
    {
        cin>>x>>y;
        printf("%d\n",lca(x,y));
    }
    return 0;
}

SP14932 LCA - Lowest Common Ancestor

照着LCA模板写咯。

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,x,y,t,q,v,cnt,f[N][21],dep[N],head[N];
struct node
{
    int to,next;
}e[N<<1];
void add(int x,int y)
{
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void dfs(int u,int father)
{
    dep[u]=dep[father]+1;
    f[u][0]=father;
    for(int i=1;i<=20;i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        v=e[i].to;
        if(v!=father)dfs(v,u);
    }
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--)
    {
        if(dep[f[x][i]]>=dep[y])x=f[x][i];
        if(x==y)return x;
    }
    for(int i=20;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    for(int cas=1;cas<=t;cas++)
    {
        memset(head,-1,sizeof(head));
        cnt=0;
        cin>>n;
        for(x=1;x<=n;x++)
        {
            cin>>m;
            while(m--)
            {
                cin>>y;
                add(x,y);
                add(y,x);
            }
        }
        dfs(1,0);
        printf("Case %d:\n",cas);
        cin>>q;
        while(q--)
        {
            cin>>x>>y;
            printf("%d\n",lca(x,y));
        }
    }
    return 0;
}

P3865 【模板】ST表

RMQ问题,Range Maximum(Minimum) Query,询问某个区间内的最大值或最小值。
显然,可以用线段树解决这一问题,AC代码(用时1.61s):

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,x,y,a[N],tr[4*N];
void build(int i,int l,int r)
{
    if(l==r)
    {
        tr[i]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
    tr[i]=max(tr[2*i],tr[2*i+1]);
}
int query(int i,int l,int r,int x,int y)
{
    if(l>y||r<x)return 0;
    if(l>=x&&r<=y)return tr[i];
    int mid=l+r>>1;
    return max(query(2*i,l,mid,x,y),query(2*i+1,mid+1,r,x,y));
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        cin>>x>>y;
        printf("%d\n",query(1,1,n,x,y));
    }
    return 0;
}

没有修改操作的条件下,则可使用ST算法,相比于线段树,它的运行速度更快,可以做到O(nlogn)的预处理,O(1)回答每次询问。
ST算法,AC代码(用时989ms):

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,x,y,k,a[N],lg[N],f[N][21];//lg[i]表示log2(i)向下取整的值,f[i][j]表示从i开始的连续2^j个数的最大值,即区间[i,i+2^j-1]的最大值
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    lg[0]=-1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i][0]=a[i];//从i开始的连续2^0个数的最大值就等于a[i]本身
        lg[i]=lg[i/2]+1;//预处理log2(i),因为cmath库中自带的函数log2(x)速度较慢
    }
    for(int j=1;j<=20;j++)//O(nlogn)的预处理
        for(int i=1;i+(1<<j)-1<=n;i++)//i+2^j-1不能超过边界n
        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//把[i,i+2^j-1]分成左区间[i,i+2^(j-1)-1]和右区间[i+2^(j-1),i+2^j-1],取较大值
    while(m--)
    {
        cin>>x>>y;
        k=lg[y-x+1];//k为方程2^k<=y-x+1的解的最大值,即log2(y-x+1)向下取整
        printf("%d\n",max(f[x][k],f[y-(1<<k)+1][k]));//取左区间[x,x+2^k-1]和右区间[y-2^k+1,y]的较大值(左右区间有重合部分)
    }
    return 0;
}