倍增_ST表与LCA

ST表

静态查询区间最值。

P3865 【模板】ST 表

ll f[100001][20];
ll n, m, a[100001];

void ST_make()
{
    for (int i = 1; i <= n; ++i)
        f[i][0] = a[i];
    ll t = log(n) / log(2) + 1;
    for (int j = 1; j < t; ++j)
        for (int i = 1; i <= n - (1 << j) + 1; ++i)
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

ll ST_q(ll l, ll r)
{
    ll k = log(r - l + 1) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    ST_make();
    for (int i = 1; i <= m; ++i)
    {
        ll l = read(), r = read();
        printf("%lld\n", ST_q(l, r));
    }
    return 0;
}

LCA

P3379 【模板】最近公共祖先（LCA）

邻接表存图。

struct node{...};
void add(...){}

ll dep[500010], fa[500010][21], lg[500002];
ll head[500010], tot;
ll n, m, s;

void dfs(ll now, ll fath)
{
    fa[now][0] = fath;
    dep[now] = dep[fath] + 1;
    for (int i = 1; i <= lg[dep[now]]; ++i)
        fa[now][i] = fa[fa[now][i - 1]][i - 1];
    for (int i = head[now]; i; i = t[i].nxt)
        if (t[i].to != fath)
            dfs(t[i].to, now);
}

ll LCA(ll x, ll y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    while (dep[x] > dep[y])
        x = fa[x][lg[dep[x] - dep[y]] - 1];
    if (x == y)
        return x;
    for (int k = lg[dep[x]] - 1; k >= 0; --k)
        if (fa[x][k] != fa[y][k])
            x = fa[x][k], y = fa[y][k];
    return fa[x][0];
}

int main()
{
    n = read();
    m = read();
    s = read();
    for (int i = 1; i <= n; ++i)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
        
    for (int i = 1; i < n; ++i)
    {
        ll x = read(), y = read();
        add(x, y);
        add(y, x);
    }
    
    dfs(s, 0);
    for (int i = 1; i <= m; ++i)
    {
        ll x = read(), y = read();
        printf("%lld\n", LCA(x, y));
    }
    return 0;
}