Permutation（线段树 + 单点更新）

Problem F
Permutation
Input: Standard Input

Output: Standard Output

 

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 S₁, S₂ ,…, S_k. 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 S₁, S₂ ,…, S_k.(0≤S_i≤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                            Output for Sample Input

4 3 2 1 0 3 1 0 0 4 2 1 1 0 4 1 2 1 0

3 2 1 2 1 3 3 2 4 1 2 4 3 1

---

Problemsetter: Abdullah al Mahmud

Special Thanks: Manzurur Rahman Khan

 

       题意：

       给出 T（1 ~ 10），代表有 T 个 case，每个 case 给出一个 N （1 ~ 50000），给出 N 个数，后给出式子 M = ，输出第 M 个 1 ~ K 的序列是什么。

 

       思路：

       线段树 + 单点更新。观察式子，反过来看，比如求K = 4 中的排列 3 2 4 1 是属于第几个排列，那么就是等于

       2 X 3！+ 1 X 2！ + 1 X 1！ + 0 X 1！，得出来的式子刚好与给出的式子 M 吻合，说明 Si 是寻找序列的第 Si 个数。得出来之后用线段树维护即可。

 

       AC：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX = 50005;

int sum[MAX * 3];
int num[MAX];

void push_up (int node) {
        sum[node] = sum[node << 1] + sum[node << 1 | 1];
}

void build (int node, int l, int r) {
        if (l == r) {
                sum[node] = 1;
        } else {
                int mid = (r + l) >> 1;
                build(node << 1, l, mid);
                build(node << 1 | 1, mid + 1, r);
                push_up(node);
        }
}

void updata (int node, int l, int r, int i) {
        if (l == r) {
                if (l == i) sum[node] = 0;
                return;
        }

        int mid = (r + l) >> 1;
        if (i <= mid) updata(node << 1, l, mid, i);
        else updata(node << 1 | 1, mid + 1, r, i);
        push_up(node);
}

int query (int node, int l, int r, int k) {
        if (l == r) return l;

        int mid = (r + l) >> 1;
        if (k < sum[node << 1]) return query(node << 1, l, mid, k);
        return query(node << 1 | 1, mid + 1, r, k - sum[node << 1]);
}

int main() {
        int t;
        scanf("%d", &t);

        while (t--) {
                int n;
                scanf("%d", &n);
                build(1, 1, n);

                for (int i = 0; i < n; ++i) {
                        scanf("%d", &num[i]);
                }

                for (int i = 0; i < n; ++i) {
                        int in = query(1, 1, n, num[i]);
                        printf("%d", in);
                        updata(1, 1, n, in);
                        i == n - 1 ? printf("\n") : printf(" ");
                }
        }

        return 0;
}