yummy
2019-05-27 00:52:04
一句话，给出一个全排列，求它是第几个全排列，叫做康托展开。
另一句话，给出全排列长度和它是第几个全排列，求这个全排列，叫做逆康托展开。
这里，全排列的顺序定义和火星人中的定义是一样的。
对于一个全排列，第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变成了
例2.把1,4,5,2,3变成变进制数
最后，1,4,5,2,3变成了
我们看到，第i位的值就是
//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);我们看到，刚才的方法有两重循环，时间复杂度为
只要把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
}这里所有数字都是单点修改，所以我没写懒标记。
线段树这种东西，你们的码风应该比我好，常数也应该比我小，就不展示了。
你都看到这儿了，还不去试一试?
接下来，我们先把给出的数据转成变进制形式。线段树都写的出来的人，这种小事应该不用讲吧。
我们要完成的工作就是，对于每个数位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代码
当初我为什么不用树状数组呢？ 因为线段树的两个子树恰好都是一样大小的，方便理解。
这玩意儿可以进行状压dp，求对应下标以及还原成全排列时可以更快一些。
一个人想做出一道题，先要有足够的自信。如果我当时把它当成一道紫题，那么我可能现在都没写出标程；但是，我一开始不知道它是紫题，也不知道它叫康托展开，只是看做一道黄题的线段树优化，对自己有足够信心，就可以发挥你的潜力。
你如果愿意，还可以作死一些：