[UVa-11525] Permutation 树状数组求kth element+康托展开

题面

传送门: UVa-11525

题目大意:
输出$1..n$的全部排列字典序大小的第$\sum_{i=1}^{k} S_i * (K-i)!$个

样例

Sample Input
4
3
2 1 0
3
1 0 0
4
2 1 1 0
4
1 2 1 0

Sample Output
3 2 1
2 1 3
3 2 4 1
2 4 3 1

思路

康托展开了解一下

$$X = a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[1]*0!$$

其中a[i]为第$i$位往右边的数里第几大
其实和数位dp一个道理。
具体的栗子（摘自cnblog）

$$如我想知道321是{1,2,3}中第几个大的数可以这样考虑 ：\\\\\ 　　第一位是3，当第一位的数小于3时，\\\\ 　　那排列数小于321 如 123、 213 ，小于3的数有1、2 。\\\\ 　　所以有2*2!个。再看小于第二位2的：小于2的数只有一个就是1 ，\\\\所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个 。\\\\所以321是第6个大的数。 \\\\2*2!+1*1!是康托展开。$$

然后是树状数组（Fenwick树）求第k小

这其实是一个反向枚举构造+二分的过程

具体看代码实现吧。

代码

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
#define lowbit(x) (x&-x)
int c[maxn], K;

void add(int pos)
{
	while(pos<=K){
		c[pos]++;
		pos+=lowbit(pos);
	}
}

int query(int pos)
{
	int res=0;
	while(pos>0){
		res+=c[pos];
		pos-=lowbit(pos);
	}
	return res;
}

int BS(int num)
{
	int l=0,r=K+1;
	while(l<r-1){
		int mid=(l+r)/2;
		if(mid-query(mid)>=num) r=mid;
		else l=mid;
	}
	return r;
}

int main(int argc, char *argv[])
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&K);
		memset(c,0,sizeof(c));
		for(int i=0;i<K;i++)
		{
			int t;
			scanf("%d",&t);
			t++;
			int k=BS(t);
			printf("%d%c",k,(i==K-1)?'\n':' ');
			add(k);
		}
	}
	return 0;
}