yummy的博客

yummy的博客

AFO了,这里记录yummy的退役生活。

浅谈康托展开

posted on 2019-05-27 00:52:04 | under Yummy的OI技巧 |

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

//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进制就可以了。

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的时间就求出左侧小于自己的数的个数了。

//从这儿开始,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的数量,如果不够,答案就在右子树,否则在左子树上继续找。

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);
}
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)$