我是从zoj的promlem classification里面找到这个题目的，开始时想不到什么好方法，企图从零开始一步一步建树。最后还是没想到建树的算法。
   后来查zoj forum，有人提到cartesian tree，于是google到了这方面的算法和数据结构。cartesian tree又叫randomized binary search tree，它是节点带权的二叉树，在插入新节点时，并非像平衡树那样做rebalance，而是维持父节点和子节点之间的权的大小关系(heap order)，即要么父节点的权总是大于子节点的权，要么反之。NIST的网站还介绍了cartesian tree节点的插入和删除算法。大致如下：
    插入：

InsertNode(Node * newNode, Node * tree)
{
     if (newNode->key < tree->key)
     {
           tree->left = InsertNode(newNode, tree->left);
           if (tree->left->priority > tree->priority)    // 假定父节点的权大
                tree = TurnRight(tree);
      }
      else 
      {
          // omited      

      }


}

    删除：

DeleteNode(Key key, Node * tree)
{
      if(key < tree->key)
      {
           tree->left = delete(key, tree) 
       }
      //omited  
}

     然而直接的建立cartesian tree会导致超时，假设最终的树的所有节点都只有右孩子，并且插入时，总是插入最右节点，那复制度将会是O(n!)。

--------------------------------------------------------------------------------

    后来又经过查阅资料，发现可以用qsort＋RMQ的方法。首先，对所有的节点，以key值排序，这样得到的结果为最终cartesian tree的中序遍历。再根据priority值，从上到下找到根节点，以及根节点的左右子树的根节点。。。
    其中时间的消耗是：排序时间＋找所有子树的根的时间。快速排序的平均复杂度为O(nlog2(n))，而利用RMQ可以在O(nlog2(n))内建立RMQ的矩阵，并在O(1)时间内查找任意范围内的最大priority节点对应的索引。
    RMQ算法主要分两部分：（1）建立RMQ的matrix，（2）查找
    （1）需要计算matrix[i][j]其中1<=i<=n, 0<=j<=[log2(n)]（上去整）
    matrix[i][j]的含义为从i开始的宽度为2^j的范围内，priority最大的节点的位置
                      {  matrix[i][j-1]              priority(matrix[i][j-1]) > priority(matrix[i+2^(j-1)][j-1])
    matrix[i][j] ={
                      { matrix[i+2^(j-1)][j-1]   否则
    （2）查找RMQ(i, j)，RMQ(i, j)的含义为从i开始到j为止的范围内，priority最大的节点的位置
    计算k=max{r|2^r < j-i+1}
                      {  matrix[i][r]                priority(matirx[i][r]) > priority(matrix[j-2^r+1][r]
    RMQ(i, j) =   {
                      { matrix[j-2^r+1][r]       否则

--------------------------------------------------------------------------------

  此问题还有一种最快的方法。考虑到对所有的输入节点做针对key的排序后，得到的数组为cartesian tree的中序遍历。

1.  现在我们从左到右，一边顺序遍历数组，一边建立cartesian tree。
2. 假设我们已经遍历到数组的第i个元素，并相应建立了有i个节点组成的cartesian tree，那么第i+1个节点必定在由i+1个节点组成的cartesian tree的最右路径的最右端点。
3. 我们原i几点的cartesian tree的最右路径的最右端点出发往上查找第一个priority比i+1节点大的节点，如果找到了，就把i+1节点的左子树设为那个节点的右子树，把那个节点的右子树设为i+1节点。如果找不到，则把i+1节点的左子树设为原树的根，并把i+1节点设为新根。
4. 需要主意的是，必须从下到上搜索最右路径，而不是从上到下。因为从上到下会出现O(n!)的复杂度，而从下到上的过程中，没个几点最多被走过一次，因为被走过的节点必被设为某个点的左子树，不再可能出现在最右路径中，所有有O(n)的复杂度。

--------------------------------------------------------------------------------

 最后给一下结果：第一种方法超时，RMQ为0.95秒，最后一种方法为0.51秒.