分析
简述“康托展开”
康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有\(n\)个数\((1,2,3,4,…,n)\)，可以有组成不同(\(n!\)种)的排列组合，康托展开表示的就是是当前排列组合在\(n\)个不同元素的全排列中的名次。式子表示：
\[X=\sum_{i=1}^{n}a_i*(i-1)!
\]
\]
\(\rightarrow\)
\[X=a_n*(n-1)!+a_{n-1}*(n-2)!+...+a_i*(i-1)!+...+a_1*0!
\]
\]
其中, \(a_i\)为整数，并且\(0\leq a_i\leq i, 0 < i \leq n,\) 表示当前未出现的的元素中排第几个，这就是康托展开。
推论
根据康托展开，\(S_i\)就是第\(i\)位上可选的数中比第\(i\)位上应选的数小的数的个数。那么此题转化为求总区间第\(S_i+1\)大。一颗权值线段树解决问题，不用持久化。康托展开的排名也是基于0的，所以也不用调用STL的last_permutation().
算法流程
- 用权值线段树求出总区间第\(S_i+1\)大，记答案为\(ans\)并输出
- 将权值线段树的\([ans,ans]\)叶节点置0
就这么简单
时间复杂度
对于单组数据，执行一次上述算法流程需要\(O(\log k)\)时间，而要执行\(k\)次，所以单组数据的时间复杂度为\(O(k\log k)\)。有\(T\)组数据所以总时间复杂度为\(O(T\cdot k\log k)\)
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define rg register
template<typename T>T read(T&x)
{
T data=0;
int w=1;
char ch=getchar();
while(ch!='-'&&!isdigit(ch))
ch=getchar();
if(ch=='-')
w=-1,ch=getchar();
while(isdigit(ch))
data=data*10+ch-'0',ch=getchar();
return x=data*w;
}
using namespace std;
const int MAXK=5e4+7;
struct SegTree
{
int sum;
}ST[MAXK<<2];
#define root ST[o]
#define lson ST[o<<1]
#define rson ST[o<<1|1]
void pushup(int o)
{
root.sum=lson.sum+rson.sum;
}
void build(int o,int l,int r)
{
if(l==r)
{
root.sum=1;
return;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
}
int qkth(int o,int l,int r,int rnk)
{ // 边找边删，简化操作
if(l==r)
{
root.sum=0;
return l;
}
int mid=(l+r)>>1,ans;
if(rnk<=lson.sum)
ans=qkth(o<<1,l,mid,rnk);
else
ans=qkth(o<<1|1,mid+1,r,rnk-lson.sum);
pushup(o);
return ans;
}
int main()
{
// freopen("UVa11525.in","r",stdin);
// freopen("UVa11525.out","w",stdout);
int T;
read(T);
while(T--)
{
memset(ST,0,sizeof(ST));
int k;
read(k);
build(1,1,k);
for(rg int i=1;i<=k;++i)
{
int s; // 不用开s数组，节省空间
read(s);
printf("%d%c",qkth(1,1,k,s+1),i==k?'\n':' ');
}
}
}
Hint
这题卡输出格式，必须按我那样写，不然会WA。（我就WA了好几次。）