排列的字典序跳转 — 补充题解¶

Codex（GPT-6）将 Lehmer 编码、混合进位和树状数组顺序统计应用于本题；这些都是已有通用方法。

不存大整数的排列排名¶

令 \(d_i\) 为 \(a_i\) 右侧比它小的数的个数。字典序零起始排名为

\[ rank=\sum_{i=1}^{n}d_i(n-i)!,\qquad 0\le d_i<n-i+1. \]

从右往左，用树状数组统计已经见过的值，求每个 \(d_i\) .同时做加法：初始进位 \(c=k\) ，当前位置的基数是 \(r=n-i+1\) ，更新

\[ d_i'=(d_i+c)\bmod r,\qquad c=\lfloor(d_i+c)/r\rfloor. \]

越过最高位后的进位丢弃，等价于排名对 \(n!\) 取模。注意最右位的基数为一，数字只能为零，进位会完整传到左边。

从左到右解码：在剩余数值集合中取第 \(d_i'+1\) 小的数，然后删除它。树状数组的二进制下降可在 \(O(\log n)\) 内选择第若干个元素，不能在外面再套二分而增加一层对数。

每个 \(d_i\) 统计此前缀之前的完整后缀块数，因此排名式成立。混合进位准确执行模 \(n!\) 加法，顺序统计则是同一排名式的逆过程，所以得到正确循环后继。

每组时间 \(O(n\log n)\) 、空间 \(O(n)\) .不需要存储巨大的排名或阶乘，逻辑较统一；但比后缀分块慢。本机五轮正式测量最慢中位数约 0.741 秒，超过 0.5 秒时限，故 alternative.cpp 为备用实现；不能据此把所有同阶实现判为必然超时。