唉，没有《金牌之路》就是不爽，这道题目又说是那本书上有的，好像要用到max heap和min heap。
Any way, I can use my own way now.
把box的内容按照输入的顺序存放到array中。我们看到u(N)就是GET操作，相当于在array的前u(N) 个元素中找i-minimum元素。如果array的前u(N)个元素按递增排序好了，那么只要取array[i]就行了。
现在的关键是提高排序的速度。假设u(k)的时候，array[0] .... array[u(k)-1]已经排好序，那么只要先对array[u(k)] ... array[u(k+1)-1]排序，再把二者合并起来就行了。C++ STL提供了所有的功能，sort和merge函数可以直接拿来用。

1. 建造过程中，对每个节点拥有的子节点排序，排序的根据是每个子节点的子节点个数。
2. 在比较两棵树时，我递规地比较他们的子树能否相同，也就是从上到下递规的遍历两颗树。
   1. 对于每个节点，我将他的字节点分组，也是根据该子节点拥有的字节点树，由于先前已经对字节点排序过了，所以分组也很容易。只要两边的组里面出现可以相同的匹配，就算该组是相同的。再接下去比较下一组。
   2. 所谓组之间地相同匹配，我的想法是，对于第一组的任一节点，从第二组中找相同的节点（以及他们的孩子），如果找到了，就做标记，并继续为第一组的下一个节点找，如果找不到，就说明不可能有相同匹配。

后来是看了Lee.Mars的算法，大概思想如下：

1. 输入序列是对一颗树的遍历生成的，该题目即是树的同构判断。
2. 因为遍历的规则未确定，所以生成的序列不同。
3. 制定一种遍历规则，对输入的序列规则化，判断最终的序列是否相同。

规则化的方法如下：

1. 将序列分解为几个子序列，代表不同的子树。
2. 对子序列递规地规则化。
3. 对规则化后地子序列排序，并合成后返回。
   

1. 首先，对一个节点的路径，可以用二进制表示，而不需要用char表示，这样一方面在后面排序时有好处，另一方面节省内存。
2. 输入所有的节点后，对节点排序，先对路径长度排（即对level），在对节点在同level的左右关系排。这样排好以后，一方面对最后的打印有好处，另一方面也方便建树。
3. 开始建树，由于上面已经按level排好序，所以只要依次按照路径把节点插入到树中的相应位置就可以了。如果在按路径查找插入点的时候发现路径有空位（即不能走下去了），则说明不完整。
4. 按照level打印树，只要依次打印排好序的节点就行了。

    我是从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秒.

1. 确定多边行的有效性
2. 计算面积

确定多边形的有效性算法如下：

• 如果该多边形的边数小于3，则视为无效
• 如果该多边形的变数等于3，视为有效
• 如果变数大于3，则对于没一条边，确保与它相邻的边不与它重合，与它不相邻的边，不与它相交。

为检查线段(i, k)和(k, j)重合，只需：

• (i, k)和(k, j)平行，即(i, k)×(k, j)=0
• j在以i, k为对角的矩形内，或i在以j, k为对角的矩形内。

为检查线段(i, j)与线段(m, n)是否相交，只需：

• (i, m)×(m, n)与(j, m)×(m, n)异号，则线段(i, j)与直线(m, n)相交
• (m, i)×(i, j)与(n, i)×(i, j)异号，则线段(m, n)与直线(i, j)相交
• 如果以上两点同时成立，则可得出线段(m, n)与线段(i, j)相交
• 如果以上叉乘有任何一个为0，如(i, m)×(m, n)==0，则如果i在线段(m, n)上，则相交

最后一步要计算面积，可以用测量师公式(A Surveryor's formula)：

一个n边形A1，A2，A3，...，An，其顶点按逆时针方向配置，且坐标分别为

Ak = (xk, yk)，k=1, 2, 3,...,n

则面积为：

        n
       ----   | Xk   X(k+1) |
       \        |                 |
1/2* /       |                 |
       ----   | Yk   Y(k+1) |
       k=1
其中，X(k+1) = X1， Y(k+1)=Y1