P3850 [TJOI2007] 书架 题解

被感情伤害后弱弱地更新一篇题解。

平衡树板子题，正常建树，节点的权值就是书的编号。对于插入，有个小 trick，就是假设插入的位置为 ，那么可以将第  个节点伸展到树根位置，继续把平衡树的第  个节点伸展到根节点的左子树，显然第  个节点的右子树一定为空，这时候把新来的节点插在这个位置。当然对于最后一个询问，直接查第  个节点即可。

Code: