浅谈康托展开

## 1.康托展开是个啥 一句话，给出一个全排列，求它是第几个全排列，叫做康托展开。 另一句话，给出全排列长度和它是第几个全排列，求这个全排列，叫做逆康托展开。 这里，全排列的顺序定义和[火星人](https://www.luogu.org/problemnew/show/P1088)中的定义是一样的。 ## 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 } ``` 这里所有数字都是单点修改，所以我没写懒标记。 线段树这种东西，你们的码风应该比我好，常数也应该比我小，就不展示了。 你都看到这儿了，还不去[试一试](https://www.luogu.org/problemnew/show/P5367)? ## 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); } ``` [试试吧](https://www.luogu.org/problemnew/show/U72177) [AC代码](https://www.luogu.org/paste/9y1lxoon) ## 5.总结&感慨 当初我为什么不用树状数组呢？ 因为线段树的两个子树恰好都是一样大小的，方便理解。 这玩意儿可以进行状压dp，求对应下标以及还原成全排列时可以更快一些。 一个人想做出一道题，先要有足够的自信。如果我当时把它当成一道紫题，那么我可能现在都没写出标程；但是，我一开始不知道它是紫题，也不知道它叫康托展开，只是看做一道黄题的线段树优化，对自己有足够信心，就可以发挥你的潜力。 你如果愿意，还可以作死一些： - 块状数组，$O(N\sqrt{N})$ - 平衡树，$O(NlogN)$