题解 P5854 【【模板】笛卡尔树】

· · 题解

UPD（2025/08/07）：修复了评论区中提到的问题，感谢评论区各位同学指正！

笛卡尔树是一种非常特殊的二叉搜索树。每个节点有两个信息 (x_i,y_i)，如果只考虑 x，它是一棵二叉搜索树，如果只考虑 y，它是一个小根堆。

（根据上面的定义，Treap 本质上也是一种笛卡尔树）

在保证 x_i 递增的情况下，我们可以在线性时间复杂度内构造一棵笛卡尔树。

每次插入一个新节点时，为了确保二叉搜索树的性质得到满足（别忘了我们按照 x 递增的顺序插入），我们需要将新节点插入到尽可能靠右端的位置。

更具体地来说，我们需要维护一个从根节点一直走右儿子形成的链。我们设当前要插入的点为 u，则我们需要在这个链上找到最后一个 y 权值比 y_u 小的点 v，将 v 的右儿子设置为 u（如果不存在这样的点，那 u 就成为根节点了）；如果 v 已经有右子树了，就将 v 的右子树接在 u 的左子树下面（因为之前插入的点的 x 权值都比 u_x 小，因此这样不会破坏二叉搜索树的性质）。

维护这样一条链可以用栈实现。因为每个节点最多进栈出栈各一次，总时间复杂度是 O(n) 的。

void build()
{
 int top=0,cur=0;
 for(int i=1;i<=n;i++)
 {
  cur=top;
  while(cur&&p[sta[cur]]>p[i])
   cur--;
  if(cur)
   rs[sta[cur]]=i;
  if(cur<top)
   ls[i]=sta[cur+1];
  sta[++cur]=i;
  top=cur;
 }
}