CH 0601 Genius ACM（进阶指南（倍增与归并））

算法竞赛进阶指南，40页，倍增

本题关键点：
0、 若希望两个数值之间的差值平方和达到最大值，则需进行配对操作，即最大值与最小值相配，次大值与次小值相配，依此类推
1、 初始化两个数组：
a[MaxN]：该数组用于存储原始数据；
b[MaxN]：该数组用于保存每一段经过排序后的数据；
c[MaxN]：归并排序过程中所使用的临时存储空间；
2、 倍增方法：
目标是找到满足差的平方和 sum 不超过 k 的最长区间范围 L 和 R。每次尝试扩展一段长度为 p 的区间，初始时 p = 1。若区间 [L, R + p] 满足条件，则将 p 乘以 2；否则将 p 除以 2；
3、 快速排序与归并排序相结合的策略：
在计算区间 [L, R] 的差的平方和 sum 时，将该区间划分为两部分 [L, w] 和 [w + 1, R]。其中，[L, w] 部分的数据在数组 b 中已按升序排列。
a) 对 [w + 1, R] 这一子区间执行快速排序操作，并将结果存储于数组 b 中；
b) 将两个有序子区间 [L, w] 和 [w + 1, R] 进行归并处理，并将归并后的结果写入临时数组 c 中

    只有 该段区间[L, R] 的sum 满足 sum <= k 的时候，才把归并排序的结果写回到 数组b