我这个人很喜欢比较玄学但是优秀的算法和数据结构。

众所周知，我们考试的时候经常遇到毒瘤出题人卡算法。但是我们也知道：“如果我自己都不知道我在干什么，你就别想卡我啦。”

所以说 天下第一！(不是CCF准用 c++14了嘛)

简单提一下 ,给一个使用示例吧:

这样就可以支持使用 生成区间 内的随机数了。

当然把宏定义里的类型 改成其他类型也是可以的。

需要注意的是 的范围是 (UINT_MAX) 但是可以用来生成负数，但是我们应当将绝对值小的作为 。如果需要更大的随机数，我们使用 ,范围为 (ULLONG_MAX)。

最后为了防止邪教出题人卡 ,我们可以使用更好的种子:

算法思想是随机取一个键值 ，把序列分为三段：小于 的，等于 的，大于 的。实现考虑分治。

我们在每一个子问题中，考虑枚举当前点下标 ,维护第一个等于 的值的下标 和第一个大于 的下标 。

对于当前点，如果它等于 我们直接把当前点融入到二号段，当前点下标 向后移一位。如果其小于 把它与二段队首交换位置，二段队首下标 向后移一位，当前点下标 向后移一位。如果其大于 ，考虑把它与空白段的队尾也就是三段的队首的前一位交换位置，三段队首下标 向前移动一位，由于当前点上的值是空白段交换来的，所以当前点下标 不动。

递归边界就是当当前区间 满足 。

最优复杂度为 ，总之效率比普通快排高就是了，而且加上了随机化可防卡。

下面是代码: