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

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)$ .不需要存储巨大的排名或阶乘，逻辑较统一；但比[后缀分块](solution.zh.md)慢。本机五轮正式测量最慢中位数约 0.741 秒，超过 0.5 秒时限，故 [alternative.cpp](alternative.cpp) 为备用实现；不能据此把所有同阶实现判为必然超时。

[题面](statement.zh.md) · [正式数据计划](tests/plan.json) · [生成器](tests/generate.py) · [测量记录](../../../docs/benchmark-R33.json)