1.用途
康托展开可以用来求一个 \(1 \sim n\) 的任意排列的排名。是一个很好的 \(\texttt{hash}\) 方法。
2.算法介绍
时间复杂度
普通的康托展开可以 \(\mathcal{O}(n^2)\) 的复杂度内求出排名，加上树状数组优化后则可以 \(\mathcal{O}(n \log n)\) 。
实现
对于一个排列 \(a\) , 统计 \(a_i\) 后面比它小的数字的个数 \(num\) ，这 \(num\) 表示着有 \(num\) 各数在它前面，而在排列里面，每级别都是阶乘级的，所以答案就累加 \(num × fac_{n-i}\) 。
用数学公式表示就是：
\[\sum_{i=1}^{n-1}fac_{n-i} ×\sum_{j=i+1}^{n} 1 \ (\rm if\ a_j<a_i) \]这样的负责度为 \(\mathcal{O}(n^2)\) 。
我们发现后面的 \(\displaystyle\sum_{j=i+1}^{n} 1 \ (\rm if\ a_j<a_i)\) 可以用树状数组来维护。于是时间复杂度降到了 \(\mathcal{O}(n \log n)\) 。
代码
未优化
void contor(int a[]) {
int num = 0, ans = 0;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (a[j] < a[i]) {
num++;
}
}
ans += num * fac[n - i];
num = 0;
}
return ans + 1;
}
优化（附树状数组板子）
int c[maxn];
int lowbit(int x) {
return x & -x;
}
void add(int x, int k) {
for (; x <= n; x += lowbit(x)) {
c[x] += k;
}
}
int ask(int x) {
int ans = 0;
for (; x; x -= lowbit(x)) {
ans += c[x];
}
return ans;
}
void contor(int a[]) {
for (int i = 1; i <= n; i++) add(a[i], 1);
int ans = 0;
for (int i = 1; i < n; i++) {
int num = ask(a[i] - 1);
add(a[i], -1);
ans += sum * fac[n - i];
}
return ans + 1;
}