【最大笛卡尔树，倍增 LCA】传送

题意概括

有 $n$ 个星球按照编号排成一行。每个星球 $i$ 有两个传送门：

• 一个传送到左侧第一个满足 $p\_j>p\_i$ 的星球。
• 一个传送到右侧第一个满足 $p\_j>p\_i$ 的星球。
• 如果对应方向不存在更大的星球，这个传送门会传回星球 $i$ 自身。

每次任务会在 $k$ 个不同星球上各放置一个机器人。机器人可以任意使用传送门，需要统计有多少个星球能够成为所有机器人的共同到达点。

机器人第一次汇合后仍然可以继续一起移动，因此答案统计的不是“第一次汇合的位置”，而是所有机器人都能够到达的星球数量。

所有询问中的星球总数为 $m$。由于

$n,m,q\le 5\times 10^5,$

不能对每个机器人单独搜索全部可达点。我们需要找到传送关系中隐藏的树形结构。

样例分析

样例中的大小序列为

$3,1,5,2,7,6,4.$

以星球 $2$ 为例，它的大小为 $1$。

左边第一个更大的星球是 $1$，右边第一个更大的星球是 $3$，因此它可以进行如下移动：

$2\rightarrow 1\rightarrow 3\rightarrow 5.$

所以星球 $2$ 能够到达的星球为

${2,1,3,5}.$

星球 $4$ 可以进行如下移动：

$4\rightarrow 3\rightarrow 5,$

因此它能够到达

${4,3,5}.$

二者能够共同到达的星球为

${3,5},$

所以任务 $2,4$ 的答案为 $2$。

这里出现了一个值得注意的现象。机器人每次都会前往一个更大的星球，并且所有可达点似乎排成了一条从当前节点向上的链。这正是最大笛卡尔树中的祖先链。

算法思路

整体思路

左右第一个更大元素之间的关系可以用最大笛卡尔树表示。在这棵树中，每个星球的两个非自环传送门都指向它的祖先，并且其中一个恰好指向父亲。因此，从一个星球出发能够到达的所有星球，正好是它在笛卡尔树上的全部祖先。

若一次任务选择了多个星球，那么所有机器人共同能够到达的位置，就是这些星球的公共祖先。所有公共祖先又恰好是它们最近公共祖先的祖先链，因此答案等于多点最近公共祖先的深度。

我们先用单调栈求出左右第一个更大位置，从而构造最大笛卡尔树。然后使用倍增预处理最近公共祖先。每次询问依次合并所有选定星球的 LCA，最终输出所得节点的深度。

从单个机器人的可达位置开始

对于星球 $i$，记：

• $L\_i$ 为左边第一个满足 $p\_{L\_i}>p\_i$ 的位置。
• $R\_i$ 为右边第一个满足 $p\_{R\_i}>p\_i$ 的位置。

如果对应位置不存在，就暂时记为 $0$。题目中的自环不会产生新的可达星球，因此分析可达范围时可以忽略自环。

如果直接按照传送门搜索，一个机器人最多可能经过 $O(n)$ 个星球。所有询问中一共给出 $m$ 个起始星球，因此最坏复杂度会达到

$O(nm),$

无法通过 $5\times 10^5$ 的数据范围。

问题的关键在于，这张有向图并不是一般的有向图。每次非自环移动都会到达一个大小更大的星球，因此不存在由多个不同星球组成的有向环。更重要的是，左右第一个更大元素正好对应笛卡尔树中的祖先关系。

为什么会想到最大笛卡尔树

最大笛卡尔树是一棵满足以下条件的二叉树：

1. 中序遍历节点的顺序为 $1,2,\ldots,n$。
2. 每个父节点的权值都大于它的子节点。

因为 $p$ 是一个排列，所以所有权值不同，这棵笛卡尔树唯一。

笛卡尔树经常用于处理“左侧第一个更大”“右侧第一个更大”和“区间最大值”之间的关系。本题的两个传送门恰好就是左右第一个更大位置，因此可以尝试研究它们与笛卡尔树父亲之间的关系。

确定笛卡尔树中的父亲

对于节点 $i$，它在最大笛卡尔树中的父亲可以由 $L\_i$ 和 $R\_i$ 确定。

如果只有一个位置存在，那么这个位置就是 $i$ 的父亲。

如果两个位置都存在，那么父亲是二者中权值较小的那个：

$ \operatorname{fa}*i= \begin{cases} L\_i, & R\_i=0,\\ R\_i, & L\_i=0,\\ L\_i, & p*{L\_i}\<p\_{R\_i},\\ R\_i, & p\_{R\_i}\<p\_{L\_i}. \end{cases} $

假设 $L\_i$ 和 $R\_i$ 都存在，并且

$p\_{L\_i}\<p\_{R\_i}.$

由于 $L\_i$ 是左边第一个更大的位置，所以区间 $(L\_i,i)$ 中的所有权值都小于 $p\_i$。

由于 $R\_i$ 是右边第一个更大的位置，所以区间 $(i,R\_i)$ 中的所有权值也都小于 $p\_i$。

因此在整个区间 $\[L\_i,R\_i]$ 中：

• $R\_i$ 的权值最大。
• $L\_i$ 的权值仅次于 $R\_i$。
• $i$ 的权值大于两个端点之间的其他所有位置。

所以在这个区间对应的笛卡尔树结构中，$R\_i$ 位于 $L\_i$ 上方，而 $i$ 直接成为 $L\_i$ 的子节点。

因此 $i$ 的父亲是 $L\_i$，也就是两个候选位置中权值较小的那个。

另一种大小关系完全对称。

传送门与祖先的关系

现在研究星球 $i$ 的两个传送门。

若 $L\_i$ 和 $R\_i$ 都存在，其中权值较小的节点是 $i$ 的父亲，权值较大的节点位于父亲上方，因此二者都是 $i$ 的祖先。

若只有一个位置存在，这个位置就是 $i$ 的父亲。

若某个方向不存在更大元素，对应传送门是自环，不会增加新的可达位置。

所以每次使用非自环传送门，机器人都会从当前节点移动到笛卡尔树中的某个祖先。因此，一个机器人能够到达的位置不会超出它的祖先链。

另一方面，每个节点的父亲一定是两个传送门之一。机器人可以不断使用指向父亲的传送门，从当前节点依次到达父亲、祖父以及更高的祖先。

所以从节点 $i$ 出发的可达集合恰好为

$\operatorname{Reach}(i)=\operatorname{Anc}(i),$

其中 $\operatorname{Anc}(i)$ 表示包含 $i$ 自身在内的全部祖先。

多个机器人的共同可达点

设一次询问选择的节点为

$x\_1,x\_2,\ldots,x\_k.$

机器人能够在节点 $v$ 汇合，当且仅当 $v$ 是每个 $x\_i$ 的祖先。

因此所有可能的汇合点组成集合

$ \operatorname{Anc}(x\_1) \cap \operatorname{Anc}(x\_2) \cap\cdots\cap \operatorname{Anc}(x\_k). $

设这些节点的最近公共祖先为

$g=\operatorname{LCA}(x\_1,x\_2,\ldots,x\_k).$

树中一组节点的所有公共祖先，恰好是它们最近公共祖先 $g$ 的全部祖先。

因此共同可达点集合为

$\operatorname{Anc}(g).$

如果令根节点深度为 $1$，那么一个节点的祖先数量恰好等于它的深度，所以本次询问的答案为

$\operatorname{dep}\_g.$

如何计算多点 LCA

倍增算法通常计算两个节点的最近公共祖先。

多点最近公共祖先可以逐个合并：

$g\_1=x\_1,$

$g\_i=\operatorname{LCA}(g\_{i-1},x\_i).$

处理完全部 $k$ 个节点后，$g\_k$ 就是所有选定节点的最近公共祖先。

这样一次询问需要进行 $k-1$ 次普通 LCA 查询。

所有询问中的节点总数为 $m$，因此查询部分的总复杂度为

$O(m\log n).$

算法流程

1. 读入 $n,q$ 和排列 $p$。

2. 从左向右扫描排列，维护一个权值严格递减的单调栈。

   对于每个位置 $i$，弹出所有权值小于 $p\_i$ 的位置。弹栈完成后的栈顶就是 $L\_i$。如果栈为空，则 $L\_i=0$。

3. 从右向左进行同样的扫描，求出每个位置的 $R\_i$。

4. 根据 $L\_i$ 和 $R\_i$ 确定父亲：

   • 如果二者都不存在，$i$ 是笛卡尔树的根。
   • 如果只有一个存在，父亲就是这个位置。
   • 如果二者都存在，选择权值较小的位置作为父亲。

5. 从父亲向儿子连边，构造有根树。

6. 从根节点开始进行广度优先遍历：

   • 根节点深度设为 $1$。
   • 记录每个节点的直接父亲。
   • 预处理倍增数组 $up\_{j,i}$，表示节点 $i$ 向上跳 $2^j$ 层后的节点。

7. 对于每次询问：

   • 读取第一个节点作为当前公共祖先 $g$。

   • 对之后的每个节点 $x$，令

     $g=\operatorname{LCA}(g,x).$

   • 输出 $\operatorname{dep}\_g$。

正确性说明

引理一：笛卡尔树中节点 $i$ 的父亲是 $L\_i$ 和 $R\_i$ 中权值较小的存在者

如果只有 $L\_i$ 存在，那么右边不存在比 $p\_i$ 更大的元素。由于 $L\_i$ 是左边距离 $i$ 最近的更大元素，所以 $i$ 在笛卡尔树中直接连接到 $L\_i$。

只有 $R\_i$ 存在时同理。

如果二者都存在，假设

$p\_{L\_i}\<p\_{R\_i}.$

根据左右第一个更大的定义，区间 $(L\_i,R\_i)$ 中除 $L\_i,R\_i$ 外的所有位置权值都小于 $p\_i$。

因此 $R\_i$ 位于 $L\_i$ 上方，而 $i$ 直接位于 $L\_i$ 下方。所以 $i$ 的父亲是 $L\_i$。

当 $p\_{R\_i}\<p\_{L\_i}$ 时结论对称成立。

因此父亲一定是二者中权值较小的存在者。

引理二：从节点 $i$ 出发能够到达的节点恰好是它的全部祖先

根据引理一，$L\_i$ 和 $R\_i$ 中至少有一个是节点 $i$ 的父亲。另一个非自环目标如果存在，则位于父亲上方，也是 $i$ 的祖先。

因此每次非自环移动都只会到达当前节点的祖先，所以所有可达节点都属于 $i$ 的祖先集合。

同时，指向父亲的传送门一定存在。机器人可以不断通过父亲传送门依次到达全部祖先。

所以节点 $i$ 的可达集合恰好是它包含自身的祖先集合。

引理三：多个节点的共同可达集合是它们最近公共祖先的祖先集合

根据引理二，一个节点是所有机器人的共同可达点，当且仅当它是所有起点的公共祖先。

设所有起点的最近公共祖先为 $g$。任何公共祖先都必须位于 $g$ 的祖先链上，而 $g$ 的每个祖先也都是所有起点的公共祖先。

因此共同可达集合恰好为 $g$ 的祖先集合。

定理：算法输出的深度等于可能汇合点数量

算法通过连续进行两点 LCA，得到所有选定节点的最近公共祖先 $g$。

根据引理三，所有可能的汇合点恰好是 $g$ 的全部祖先。

根节点深度定义为 $1$，所以 $g$ 的祖先数量等于 $\operatorname{dep}\_g$。

算法输出 $\operatorname{dep}\_g$，因此输出值恰好等于题目要求的可能汇合点数量。

实现细节与易错点

1. 单调栈中需要保持权值严格递减。由于 $p\_i$ 两两不同，弹栈条件写成

   p[st[tp]] < p[i]
   

   即可。

2. 某个方向不存在更大的星球时，题目会产生一个自环。自环不会增加新的可达位置，因此构造笛卡尔树时直接忽略。

3. 最大值所在位置是笛卡尔树的根。它的左右第一个更大位置都不存在。

4. 根节点深度必须设为 $1$。答案统计包含最近公共祖先自身，因此不能将根深度设为 $0$。

5. 树可能退化成长度为 $n$ 的链。递归 DFS 可能导致栈溢出，因此使用队列进行广度优先遍历。

6. 因为

   $2^{19}=524288>5\times 10^5,$

   倍增数组保留 $0$ 到 $19$ 共 $20$ 层即可。

7. 单点询问不需要特殊处理。它的多点 LCA 就是自身，答案自然等于该节点的深度。

参考实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 500005;
const int G = 20;

int n, q;
int p[N], l[N], r[N];
int fa[N], dep[N];
int st[N], tp;
int hd[N], to[N], nx[N], ec;
int up[G][N];

void add(int u, int v) {
    ++ec;
    to[ec] = v;
    nx[ec] = hd[u];
    hd[u] = ec;
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) {
        swap(x, y);
    }

    int d = dep[x] - dep[y];

    for (int j = 0; j < G; ++j) {
        if ((d >> j) & 1) {
            x = up[j][x];
        }
    }

    if (x == y) {
        return x;
    }

    for (int j = G - 1; j >= 0; --j) {
        if (up[j][x] != up[j][y]) {
            x = up[j][x];
            y = up[j][y];
        }
    }

    return up[0][x];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> q;

    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }

    tp = 0;

    for (int i = 1; i <= n; ++i) {
        while (tp && p[st[tp]] < p[i]) {
            --tp;
        }

        if (tp) {
            l[i] = st[tp];
        }

        st[++tp] = i;
    }

    tp = 0;

    for (int i = n; i >= 1; --i) {
        while (tp && p[st[tp]] < p[i]) {
            --tp;
        }

        if (tp) {
            r[i] = st[tp];
        }

        st[++tp] = i;
    }

    int rt = 0;

    for (int i = 1; i <= n; ++i) {
        if (!l[i] && !r[i]) {
            rt = i;
        } else if (!l[i]) {
            fa[i] = r[i];
        } else if (!r[i]) {
            fa[i] = l[i];
        } else if (p[l[i]] < p[r[i]]) {
            fa[i] = l[i];
        } else {
            fa[i] = r[i];
        }

        if (fa[i]) {
            add(fa[i], i);
        }
    }

    queue<int> qu;
    dep[rt] = 1;
    qu.push(rt);

    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();

        for (int e = hd[u]; e; e = nx[e]) {
            int v = to[e];

            dep[v] = dep[u] + 1;
            up[0][v] = u;

            for (int j = 1; j < G; ++j) {
                up[j][v] = up[j - 1][up[j - 1][v]];
            }

            qu.push(v);
        }
    }

    while (q--) {
        int k, x, g = 0;
        cin >> k;

        for (int i = 1; i <= k; ++i) {
            cin >> x;

            if (i == 1) {
                g = x;
            } else {
                g = lca(g, x);
            }
        }

        cout << dep[g] << '\n';
    }

    return 0;
}

复杂度分析

使用两次单调栈分别求左右第一个更大位置。每个节点最多入栈和出栈一次，因此这部分时间复杂度为

$O(n).$

构造笛卡尔树需要 $O(n)$ 时间。

倍增数组共有 $O(\log n)$ 层，每个节点都需要预处理这些层，因此倍增预处理时间复杂度为

$O(n\log n).$

一次两点 LCA 查询的时间复杂度为

$O(\log n).$

设所有询问中给出的节点总数为

$m=\sum k.$

每个节点至多参与一次 LCA 合并，所以全部询问的总时间复杂度为

$O(m\log n).$

总时间复杂度为

$O((n+m)\log n).$

单调栈、树结构和普通数组占用 $O(n)$ 空间。倍增数组占用

$O(n\log n)$

空间，因此总空间复杂度为

$O(n\log n).$