首先切牌肯定有性质，但是你认为我没有脑子，建图倍增可以快速将最终序列的每个位置对应的原位置求出来。
相当于我要循环位移目前数列，使得按照给定关键字排序后字典序最小。
借用后缀排序的思路，维护一个长度的倍增数组，显然发现第 \(lg\) 层只需记录 \(\frac{n}{lg}\) 个关键结点，所以复杂度其实是 \(O(n + n\log n)\) 的，用基数排序也行。
首先切牌肯定有性质，但是你认为我没有脑子，建图倍增可以快速将最终序列的每个位置对应的原位置求出来。
相当于我要循环位移目前数列，使得按照给定关键字排序后字典序最小。
借用后缀排序的思路，维护一个长度的倍增数组，显然发现第 \(lg\) 层只需记录 \(\frac{n}{lg}\) 个关键结点，所以复杂度其实是 \(O(n + n\log n)\) 的，用基数排序也行。