浅谈康托展开

1.康托展开是个啥

一句话，给出一个全排列，求它是第几个全排列，叫做康托展开。

另一句话，给出全排列长度和它是第几个全排列，求这个全排列，叫做逆康托展开。

这里，全排列的顺序定义和火星人中的定义是一样的。

2.暴力康托展开

对于一个全排列，第i为有n+1-i种选择，如果用变进制数表示，这一位就是n+1-i进制的。如果这一位选择了第k种情况，那么对应的变进制数的这一位就是k。

为了方便起见，通常以0起下标。

举个栗子：例1.12345变成变进制数是(00000)

首位1是5种选择{1,2,3,4,5}的第1种，故变为0
次位2是4种选择{2,3,4,5}的第1种，故变为0 【解释：为什么是4种选择，其实是还没有使用过的数字的总数，下同】
中间位3是3种选择{3,4,5}的第1种，故变为0
次低位4是2种选择{4,5}的第1种，故变为0
末位5是1种选择的{5}第1种，故变为0

最后，1,2,3,4,5变成了

(00000)_{unknown}

例2.把1,4,5,2,3变成变进制数

首位1是5种选择{1,2,3,4,5}的第1种，故变为0
次位4是4种选择{2,3,4,5}的第3种，故变为2
中间位5是3种选择{2,3,5}的第3种，故变为2
次低位2是2种选择{2,3}的第1种，故变为0
末位3是1种选择的{3}第1种，故变为0

最后，1,4,5,2,3变成了

(02200)_{unknown}

我们看到，第i位的值就是

a_i

减去它左边比它小的数的数量-1

CPP

//n表示全排列长度
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    int x=a[i];
    for(int j=1;j<=a[i];j++)
        x-=used[j];
    //used[j]表示j是否用过(1用过，0没用）
    used[a[i]]=1;
    a[i]=x-1;
}

有了变进制形式的结果，把它转换成10进制就可以了。

CPP

long long res=0;
for(int i=1;i<n;i++)
    res=(res+a[i])*(n-i);

请自己找一个全排列，试一试。
例二的结果是16，表示是第17个全排列，例一结果是0，表示第1个全排列，你算对了吗？

3.线段树康托展开

我们看到，刚才的方法有两重循环，时间复杂度为

O(N^2)

,找左侧用过的数的数量很费时间。

只要把used函数用线段树维护区间和，就可以只花log的时间就求出左侧小于自己的数的个数了。

CPP

//从这儿开始，tt是长度，n是线段树大小
for(int i=1;i<=tt;i++)
{
    scanf("%d",&a[i]);
    upd(a[i]+n);
    //upd更新一个节点
    a[i]-=sum(1,a[i],1,n,1)+1;
    //sum(x,y,l,r,root)=x到y的区间和，在l到r区间找，根节点在root
}

这里所有数字都是单点修改，所以我没写懒标记。

线段树这种东西，你们的码风应该比我好，常数也应该比我小，就不展示了。

你都看到这儿了，还不去试一试?

4.线段树逆康托展开

接下来，我们先把给出的数据转成变进制形式。线段树都写的出来的人，这种小事应该不用讲吧。

我们要完成的工作就是，对于每个数位a[i]，求出x使得x前面的数中恰好有a[i]个0。这里我们可以用二分，每次查询左子树上0的数量，如果不够，答案就在右子树，否则在左子树上继续找。

CPP

int fx(int l,int r,int x,int root)
//在l到r范围找出有x个0的位置
{
    if(l==r)
        return l;
    int mid=(l+r)>>1,sss=sum(l,mid,l,r,root);
    if(mid-l+1-sss>x)
        return fx(l,mid,x,root<<1);
    return fx(mid+1,r,x-(mid-l+1-sss),(root<<1)+1);
}

CPP

for(int i=1;i<=tt;i++)
{
    int fff=fx(1,n,a[i],1,0);
    upd(fff+n);
    printf("%d ",fff);
}

试试吧

AC代码

5.总结&感慨

当初我为什么不用树状数组呢？因为线段树的两个子树恰好都是一样大小的，方便理解。

这玩意儿可以进行状压dp，求对应下标以及还原成全排列时可以更快一些。

一个人想做出一道题，先要有足够的自信。如果我当时把它当成一道紫题，那么我可能现在都没写出标程；但是，我一开始不知道它是紫题，也不知道它叫康托展开，只是看做一道黄题的线段树优化，对自己有足够信心，就可以发挥你的潜力。

你如果愿意，还可以作死一些：

块状数组， $O(N\sqrt{N})$
平衡树， $O(NlogN)$

文章操作