HILO

· · 题解

考虑笛卡尔树。

以下标为堆的权值，值为 BST 的权值，建出笛卡尔树。

样例图片：

容易发现，在一个点如果得到 HI 的结果下一个询问一定在左孩子，否则在右孩子。

直接在笛卡尔树上算根到每个点的路径上有多少个 HILO 就行了。