ST - RMQ - LCA

void ST_create(){
    k = log2(N);
    for(int j = 1; j <= k; j++)
        for(int i = 1; i <= n - (1<<j) + 1; i++)
            F[i][j] = F[F[i][j-1]][j-1];
}

int LCA_ST_query(int x, int y){
    if (d[x] > d[y]) swap(x, y);
    for(int i = k; i >= 0; i--)
        if (d[F[y][i]] >= d[x])
            y = F[y][i];
    if (x == y) return x;
    for(int i = k; i >= 0; i--)
        if (F[x][i] != F[y][i])
            x = F[x][i], y = F[y][i];
    return F[x][0];
}

pos[u] = ++tot;
seq[tot] = u;
dep[tot] = d;

void dfs(int u, int d){
    vis[u] = true;
    pos[u] = ++tot;
    seq[tot] = u;
    dep[tot] = d;
    for(int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v, w = e[i].c;
        if (!vis[v]){
            dist[v] = dist[u] + w;
            dfs(v, d + 1);
        }
        seq[++tot] = u;
        dep[tot] = d;
    }
}

void ST_create(){
    for(int i = 1; i <= tot; i++)
        F[i][0] = i;
    k = log2(tot);
    for(int j = 1; j <= k; j++)
        for(int i = 1; i <= tot - (1<<j) + 1; i++)
            if (dep[F[i][j-1]] < dep[F[i+(1<<(j-1))][j-1]])
                F[i][j] = F[i][j-1];
            else
                F[i][j] = F[i+(1<<(j-1))][j-1];
}

int RMQ_query(int l, int r){
    int k = log2(r - l + 1);
    if (dep[F[l][k]] < dep[F[r-(1<<k)+1][k]])
        return F[l][k];
    else
        return F[r-(1<<k)+1][k];
}

int LCA(int x, int y){
    int l = pos[x], r = pos[y];
    if (l > r) swap(l, r);
    return seq[RMQ_query(l, r)];
}
全部评论

相关推荐

神哥不得了:神哥来啦~1.建议不要包装,很容易问穿2.没日常也能找到暑期3.简历模板换一下,字体和版式看着好难受,而且最好压缩到一页,技术的倒数第2和3重复啦,项目建议换两个高质量的上去,如果时间够的话,八股就把高频top50的题目多巩固几遍,吃透,注意不要找假高频,这样绝对能找到暑期
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务