自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:14:59，当前版本为作者最后更新于2019-12-27 22:50:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
 }
}