实在是太弱了看了两天4小时左右才基本把这个倍增构造看明白。。另外不得不说竞赛风格的板子虽然抄起来舒服但是对初学者而言的确不太友好……
原理
令step = 1, 2, 4, …
然后每次基数排序i : (x[i], x[i+step])对，将排序结果写回x数组中
例如x = abaab, step=1时
待排序的东西：(a,b), (b,a), (a,a), (a,b), (b, $)
很明显排序结果是(a,a)[原来的2号位置]，(a,b)[0], (a,b)[3], (b,$)[4], (b,a)[1]
所以，我们得到的新的x就是：
13012（注意，因为两个(A,b)相同，我们要给它们相同的编号）
重复此流程(step *= 2)，直到x中没有重复元素。
基数双关键字排序[1]
怎么基数双关键字排序呢？https://www.byvoid.com/blog/sort-radix 。
第二种方式是从最低有效关键字开始排序，称为**LSD(Least Significant Dight)**排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。
我们采用LSD排序。
首先，把所有东西按第二关键字排序：利用基数排序的技巧
待排序的东西：(a,b), (b,a), (a,a), (a,b), (b, $)
第二关键字排序结果（注意要稳定）[次序 -> 原数组下标]：4 1 2 0 3 ($字符最小)。即(b, $), (b,a), (a, a), (a, b), (a, b)
然后我们要把第二关键字排序的结果按第一关键字排序。注意，当我们已经知道[次序 -> 原数组下标]：4 1 2 0 3时，就相当于对这个数组，用key = x[ 这个数组[下标] ]，进行稳定排序。因为这个数组的下标是第二关键字的排序结果，这个数组[下标]表示这个下标原来对应的位置，x[位置]就是第一关键字的值。
然后我们再恢复回来原来x的值，然而[0:1]和[3:4]其实都是ab, 最后的x中我们要给它们一个相同的值。这就要求我们在遍历排序结果时维护一个计数器，当且仅当和前一个( , )不同时才给计数器+1.
稳定的基数排序[Required by 1]
这里，两次用到了稳定的基数排序的方法：
快速根据本次的sa，求出下次按第二关键字排序的sa
第二点，怎么在已知本次排序出的sa [Ref. 2]的情况下，快速求出下一次[Ref. 1]呢？
一般情况下，我们只要把这次算出来的sa中每个的位置 – step就行了：因为这一次pos就是下一次pos – step的第二关键字的位置。但是如果sa[i] – step < 0怎么办？这样我们就认为是最小的(因为这个时候第二关键字是$)，所以：
先扫一遍，找出所有的sa < step的，然后加到新的sa的最前面，之后在把正常情况扫一遍，依次以sa[i]-step加入新sa。
代码