最低公共祖先

第一次记录一个大坑
本题用向上标记法其实就已经够了，但是本$sb$非得奔着复习倍增法的想法，我写了倍增，然后$debug$了一整天
由于倍增法中将$0$记为哨兵，任何跳到0的操作都是不能被执行的，所以对树中结点编号一定不能有0!!!
本题中结点含有负数，因此要先离散化，离散化的时候要从1开始!!!

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10, M = N * 2;
int n, m;
int pre[N], in[N];
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][16], q[M], book[N];
unordered_map<int, int> pos;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    int hh = 0, tt = 0; q[0] = root;
    while (hh <= tt)
    {
        int t = q[hh ++];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                fa[j][0] = t;
                q[++ tt] = j;
                for (int k = 1; k <= 15; k ++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}
int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 15; k >= 0; k --)
        if (depth[fa[a][k]] >= depth[b]) a = fa[a][k];
    if (a == b) return a;
    for (int k = 15; k >= 0; k --)
        if (fa[a][k] != fa[b][k]) 
            a = fa[a][k], b =fa[b][k];
    return fa[a][0];
}

int build(int pl, int pr, int il, int ir)
{
    int root = pre[pl], k = root - il, l, r;
    if (il < root) 
    {
        l = build(pl + 1, pl + k, il, il + k - 1);
        add(root, l);
    }
    if (ir > root)
    {
        r = build(pl + k + 1, pr, il + k + 1, ir);
        add(root, r);
    }
    return root;
}

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i ++) 
    {
        cin >> pre[i];
        book[i] = pre[i];
    }
    sort(book + 1, book + n + 1);  // 将中序排序
    for (int i = 1; i <= n; i ++) 
    {
        pos[book[i]] = i;  // 建立映射
        in[i] = i;  // 建立离散化后的中序映射
    }
    for (int i = 1; i <= n; i ++) pre[i] = pos[pre[i]];  // 建立离散化后的前序序列

    memset(h, -1, sizeof h);
    int root = build(1, n, 1, n);

    bfs(root);
    while (m --)
    {
        int a, b; cin >> a >> b;
        bool has_a = false, has_b = false;
        if (pos.count(a))
        {
            a = pos[a]; has_a = true;
        }
        if (pos.count(b)) 
        {
            b = pos[b]; has_b = true;
        }
        if (has_a && has_b) 
        {
            int p = lca(a, b);
            if (p == a) printf("%d is an ancestor of %d.\n", book[a], book[b]);
            else if (p == b) printf("%d is an ancestor of %d.\n", book[b], book[a]);
            else printf("LCA of %d and %d is %d.\n", book[a], book[b], book[p]);
        }
        else if (has_a) printf("ERROR: %d is not found.\n", b);
        else if (has_b) printf("ERROR: %d is not found.\n", a);
        else printf("ERROR: %d and %d are not found.\n", a, b);
    }
    return 0;
}