1785专题

POJ 1785 treap 或 RMQ

本题大意就是。 建立一颗树,每个结点有两个关键字,要求第一个关键字满足二叉搜索树的性质,第二个结点满足堆的性质 首先,要把所有结点按照第一个关键字按非递减排序,这样之后,每个结点左边的结点都比该结点的第一个关键字小,右边的则第一个关键字都比他大。 这样的话按顺序每次插入右子树,因为要满足二叉搜索树的性质, 插入之后不能满足堆的性质时就左旋。 #include <iostream>