Permutation （樹狀數組）

Given N and K find the N-th permutation of the integers from 1 to K when those permutations are

lexicographically ordered. N starts from 0. Since N is very large N will be represented by a sequence

of K non-negative integers S1, S2, . . . , Sk. From this sequence of integers N can be calculated with

the following expression.

Input

First line of the input contains T (≤ 10) the number of test cases. Each of these test cases consists of

2 lines. First line contains a integer K (1 ≤ K ≤ 50000). Next line contains K integers S1, S2, . . . , Sk.

(0 ≤ Si ≤ K − i).

Output

For each test case output contains N-th permutation of the integers from 1 to K. These K integers

should be separated by a single space.

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

題目大概:

有t組樣例，每組樣例有個數k，接下來k個數，分别試s1，s2...sk。

最終是求出k個數的第N個全排列是什麼，N 用題目給出的公式算出。

思路：

由于題目要求全排列是按字典序大小來的，那麼如果一個數列1  2  3  4.

當i=1時，s1=1時，符合條件的全排列，一定時 2 . . . 到2 . . .的某個數，一定是2開頭。

因為（k-i）是剩下的i個數的全排列，第si，就是本位應該是第si+1大的數開頭。

是以，最終隻需要一位一位求出第i位的數就可以了，第i位的數是剩下的數中的第si+1大的數。

#include <bits/stdc++.h>

using namespace std;
const int maxn=5e4+10;
int c[maxn];
int k;
int a[maxn];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int v)
{
    while(x<maxn)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int sum=0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int work(int d)
{
    int l=1,r=k;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(sum(mid)<d)
        {
            l=mid+1;
        }
        else r=mid-1;
    }
    return l;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(c,0,sizeof(c));
        scanf("%d",&k);
        for(int i=1;i<=k;i++)
        {
            scanf("%d",&a[i]);
            add(i,1);
        }
        for(int i=1;i<=k;i++)
        {
            int ans=work(a[i]+1);
            printf("%d",ans);
            if(i!=k)printf(" ");
            add(ans,-1);
        }
        printf("\n");
    }
    return 0;
}