【题意】

我们知道1——k有K！种排列，现在给定k和n，要你按字典序输出 第n种排列的数列？

【解题方法】

BIT OR 线段树。（这段话是粘的别人的，懒的写，不过思路都一样）k最大为50000，直接算出来不可能，我发现这个n的表达式很有意思，明显（k-1）！就是表示第一次除第一个以外，剩下k-1个数的排列个数，乘一个S1就说明之前用了多少次这种排列了，根据这个 再手算了一下，发现就是，每次找第Sk个数，输出，当然已经访问过的数就要T出去

这很明显就是树状数组 （或者线段树的单点修改和查询）功能，先初始化每个都是大小为1，然后每次二分找第Sk个，找到之后，把该位置置为-1，消除该位的影响，继续找，继续输出即可。你看题目里给定的S的范围也就是顺应这个，故意把剩下几个数，S就恰好限定在这个里面。

【AC code】 
#include <bits/stdc++.h>
using namespace std;
const int maxn=50010;
int c[maxn];
int ans[maxn];
int n;
int lowbit(int x)
{
    return (x&(-x));
}
void add(int x,int v)
{
    while(x<=n){
        c[x]+=v;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++) add(i,1);
        int val;
        for(int i=1; i<=n; i++){
            scanf("%d",&val);
            int l=1,r=n;
            while(l<r){
                int mid=(l+r)/2;
                int temp=getsum(mid);
                if(temp<val+1) l=mid+1;
                else r=mid;
            }
            add(l,-1);
            ans[i]=l;
        }
        for(int i=1; i<n; i++) printf("%d ",ans[i]);
        printf("%d\n",ans[n]);
    }
}