表示之前没见过这种东西。
概念
构造
以下均假设原序列元素两两不相同。
从左至右依次加入元素，维护当前笛卡尔树的右耳子链
\[root\to rson\to rson.rson\to rson.rson.rson\dots \]至一个栈内。
设加入的节点为 \(x\)，\(t\) 为当前笛卡尔树。
-
找到栈中最靠顶部的节点 \(y\) 使得 \(val[y]<val[x]\)。
-
特判 \(y\) 为栈顶，直接 \(t[y].rson:=x\) 即可结束。
-
记栈中 \(y\) 的楼上为 \(z\)
时间 \(O(n)\)