1555: Inversion Sequence
Time Limit: 2 Sec Memory Limit: 256 MB
Submit: 478 Solved: 173

Description
For sequence i1, i2, i3, … , iN, we set aj to be the number of members in the sequence which are prior to j and greater to j at the same time. The sequence a1, a2, a3, … , aN is referred to as the inversion sequence of the original sequence (i1, i2, i3, … , iN). For example, sequence 1, 2, 0, 1, 0 is the inversion sequence of sequence 3, 1, 5, 2, 4. Your task is to find a full permutation of 1~N that is an original sequence of a given inversion sequence. If there is no permutation meets the conditions please output “No solution”.

Input
There are several test cases.
Each test case contains 1 positive integers N in the first line.(1 ≤ N ≤ 10000).
Followed in the next line is an inversion sequence a1, a2, a3, … , aN (0 ≤ aj < N)
The input will finish with the end of file.

Output
For each case, please output the permutation of 1~N in one line. If there is no permutation meets the conditions, please output “No solution”.

Sample Input
5
1 2 0 1 0
3
0 0 0
2
1 1

Sample Output
3 1 5 2 4
1 2 3
No solution

題意：
設有一個1~n的全排列，滿足給定輸入的逆序對數(shù)，求這個全排列。
例如：輸入5 1 2 0 1 0，即求一個1~5的全排列，滿足，1有一個逆序對（即1的前面有且只有1個數(shù)字大于它），2有兩個逆序對（即2前面有且只有2個數(shù)字大于它），3有零個逆序對（3前面沒有數(shù)字大于它），以此類推?？傻? 1 5 2 4。

思路：
模擬這個過程，樣例5 1 2 0 1 0中，1前面有1個數(shù)字大于它，又因為1是1~n中最小，序列中所有數(shù)字都大于它，即1前面只能有一個數(shù)字，則1前面留一個空位，即1在從左往右數(shù)第2個空位插入，得
_ 1 _ _ _ _
2前面有2個數(shù)字大于它，除去1，2在1~n中又最小，同理，2前面留兩個空位，在第3個空位插入，得
_ 1 _ 2 _ _
3前面沒有數(shù)字大于它，同理除去1、2，3是1~n中最小，則3前面留零個空位，在第1個空位插入，得
3 1 _ 2 _
4前面有1個數(shù)字大于它，同理，4前面留一個空位，在第2個空位插入，得
3 1 _ 2 4
5前面沒有數(shù)字大于它，在第1個空位插入，得
3 1 5 2 4
得到結果3 1 5 2 4。
即從1開始到n，每一個數(shù)字都去考慮，留幾個空位給后面比它大的數(shù)字，那么就要實時更新每一段區(qū)間空位的數(shù)量，使用線段樹。

#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 20000 + 5;
int tree[maxn * 4];
int buf[maxn];
int ans[maxn];

// 更新線段樹
void Update(int root) {
    tree[root] = tree[root * 2] + tree[root * 2 + 1];
    return;
}

// 遞歸構造線段樹
void Build(int root, int l, int r) {
    if (l == r) {
        tree[root] = 1;
        return;
    }
    int mid = (l + r) / 2;
    Build(root * 2, l, mid);
    Build(root * 2 + 1, mid + 1, r);
    Update(root);
    return;
}

// 找到位置插入數(shù)字
int Insert(int val, int root, int l, int r) {
    if (l == r) {
        tree[root] = 0;
        return l;
    }
    int mid = (l + r) / 2;
    int ret;
    if (tree[root << 1] >= val)
        ret = Insert(val, root * 2, l, mid);
    else
        ret = Insert(val - tree[root * 2], root * 2 + 1, mid + 1, r);
    Update(root);
    return ret;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        // memset(tree, 0, sizeof(tree));
        Build(1, 1, n);
        bool noSolution = false;
        for (int i = 1; i <= n; ++i)
            scanf("%d", buf + i);
        for (int i = 1; i <= n; ++i) {
            // 任何時候空位數(shù)小于所給逆序對數(shù)，即當前數(shù)字沒位置插入，則無解
            if (tree[1] <= buf[i]) {
                noSolution = true;
                break;
            }
            // 在第buf[i]+1個位置插入i
            ans[Insert(buf[i] + 1, 1, 1, n)] = i;
        }
        if (noSolution)
            printf("No solution\n");
        else {
            for (int i = 1; i < n; ++i)
                printf("%d ", ans[i]); 
            printf("%d\n", ans[n]);
        }
    }
    return 0;
}