应用：用来求一个求 1∼N 的一个给定全排列在所有1∼N 全排列中的排名。可以在 \(O(n^2)\) 的复杂度内求出一个排列的排名，在用到树状数组优化时可以做到 \(O(nlog n)\)。
举个例子：
当n=3时，一共有n!=6种组合。所有组合按照字典需排序如下：
123
132
213
231
312
321
那么
f("123") = 1
f("132") = 2
...
f("321")=6
下面，我将解释这个算法的原理，首先给出康托展开的公式：
给定全排列s,则\(f(s)=a_n(n-1)!+a_{n-1}(n-2)!+...+a_1*0!+1\)
其中！表示阶乘符号，\(n!=n*(n-1)*...*2*1\)，
\(a_i\)表示前面i-1位未出现过的且比s[i]小的数的数量。
举个例子：令s="24153"
第一位是2，比它小的就只有一个1了，所以只有1放在这一位，才会比它小，那后面的呢？你爱怎么排怎么排！后面有4个数，所以一共有4!种排列方法，也就是说一共有1×4!种方法。
第二位是4，比它小的有1,2,3，但是2已经在前面出现过了，所以能放在这一位的就只有1,3这2个数，而后面呢，有3个数，就有3!种排列方法，所以一共有
2×3!种方法。
第三位的1没有更小的啦，所以一共是0×2!种方法。
第四位在5后面有比5小的有3，一共1个数，1×1!种方法。
第五位其实不用考虑了，都用过了。
那么f(s)=1×4!+2×3!+0×2!+1×1!+0×0!+1=37，所以该排列的排名位37名。
而\(a_i\)和前i-1位数有关，类似动态前缀和，那么我们就可以用树状数组进行维护，每次更新只需要logn的时间，大大优化了时间复杂度。
P5367 【模板】康托展开
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;//虽然不知道这题不开long long会不会见祖宗，但保险起见还是开一下吧
ll tree[1000005];//树状数组
int n;
int lowbit(int x){
return x&-x;
}
void update(int x,int y){
while(x<=n){
tree[x]+=y;
x+=lowbit(x);
}
}
ll query(int x){
ll sum=0;
while(x){
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
const ll mod=998244353;
ll jc[1000005]={1,1};//存阶乘的数组
int a[1000005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){//预处理阶乘数组和树状数组
jc[i]=(jc[i-1]*i)%mod;
update(i,1);
}
ll ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ans=(ans+((query(a[i])-1)*jc[n-i])%mod)%mod;
update(a[i],-1);
}
printf("%lld",ans+1);//别忘了+1
return 0;
}