学步园

归并树
以1 5 2 6 3 7为例：
把归并排序递归过程记录下来即是一棵归并树：
        [1 2 3 5 6 7]
    [1 2 5]      [3 6 7]
   [1 5] [2]    [6 3] [7] 
  [1][5]        [6][3]
用对应的下标区间建线段树：（这里下标区间对应的是原数列）
            [1 6]
     [1 3]      [4 6]
  [1 2] [3]   [4 5][6]
  [1][2]      [4][5]
每次查找[l r]区间的第k大数时，在[1 2 3 4 5 6 7]这个有序的序列中二分所要找的数x，然后对应到线段树中去找[l r]中比x小的数有几个，即x的rank。由于线段树中任意区间对应到归并树中是有序的，所以在线段树中的某个区间查找比x小的数的个数也可以用二分在对应的归并树中找。这样一次查询的时间复杂度是log(n)^2。
要注意的是，多个x有相同的rank时，应该取最大的一个。

划分树
同样以1 5 2 6 3 7为例：
根据中位数mid，将区间划分成左子树中的数小于等于mid，右子树中的数大于等于mid，得到这样一棵划分树：
        [1 5 2 6 3 7]
     [1 2 3]      [5 6 7]
   [1 2]  [3]    [5 6] [7]
  [1] [2]        [5] [6] 
注意要保持下标的先后顺序不变
对每一个区间，用sum[i]记录区间的左端点left到i有几个进入了左子树，即有几个数小于等于mid
用对应的下标区间建线段树：（这里下标区间对应的是排序后的数列）
            [1 6]
     [1 3]      [4 6]
  [1 2] [3]   [4 5][6]
  [1][2]      [4][5]
每次查找[l r]区间的第k大数时，先查看当前区间[left right]下的sum[r] - sum[l - 1]是否小于等于k，如果是，则递归到左子树，并继续在[left + sum[l - 1], left + sum[r] - 1]中找第k大数；
否则，进入右子树，继续在[mid + l - left + 1 - sum[l - 1], mid + r - left + 1 - sum[r]]找第k - sum[r] + sum[l - 1]大数
这样一次查询只要logn的复杂度

对于建划分树的方法，我一开始是先建完一层，再往下递归，过了PKU2104后，交HDU2665WA，后来发现对于0 0 -1这样的数据，下一层本应该是-1 0 0，而我的程序还是0 0 -1，原因就是会有很多相同的元素等于mid。于是我就找什么是唯一的，很容易想到数组的下标，仔细观察，如果从划分树叶子回溯，相当于在对数组下标进行归并排序，于是我的问题就解决了~

思考：划分树可以求逆序数吗，划分树中如何求一个数在某个区间的ran