Number - NekoMio's Blog

题目描述#

一个排列，求出了 a 数组，其中 ai 表示第 i 个数左边有多少个数比它小

计算出原来的排列

输入#

第一行输入 n 接下来 n - 1 个整数 ai，下标从 2 开始

输出#

输出 n 个整数表示原排列

样例输入#

5
1
2
1
0

样例输出#

2
4
5
3
1

提示#

对于 20% 的数据满足：1 ≤ n ≤ 10 对于 50% 的数据满足：1 ≤ n ≤ 1000 对于 100% 的数据满足，1 ≤ n ≤ 100000 保证解存在

题解#

输入的树就是按顺序插入时比他小的数的数量
用一颗平衡树维护就可以了

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstdlib>
4
using namespace std;
5
struct Node
6
{
7
    Node *ch[2];
8
    int s, id, key;
9
    Node(int x)
10
    {
11
        key = rand();
12
        id = x;
13
        s = 1;
14
        ch[0] = ch[1] = NULL;
15
    }
16
#define size(_) ((_) ? (_)->s : 0)
17
    void Update()
18
    {
19
        s = size(ch[1]) + size(ch[0]) + 1;
20
    }
21
} * root;
22
Node *Merge(Node *A, Node *B)
23
{
24
    if (!A)
25
        return B;
26
    if (!B)
27
        return A;
28
    if (A->key < B->key)
29
    {
30
        A->ch[1] = Merge(A->ch[1], B);
31
        A->Update();
32
        return A;
33
    }
34
    else
35
    {
36
        B->ch[0] = Merge(A, B->ch[0]);
37
        B->Update();
38
        return B;
39
    }
40
}
41
typedef pair<Node *, Node *> DNode;
42
DNode Split(Node *rt, int k)
43
{
44
    if (!rt)
45
        return DNode(NULL, NULL);
46
    DNode o;
47
    if (size(rt->ch[0]) >= k)
48
    {
49
        o = Split(rt->ch[0], k);
50
        rt->ch[0] = o.second;
51
        rt->Update();
52
        o.second = rt;
53
    }
54
    else
55
    {
56
        o = Split(rt->ch[1], k - size(rt->ch[0]) - 1);
57
        rt->ch[1] = o.first;
58
        rt->Update();
59
        o.first = rt;
60
    }
61
    return o;
62
}
63
void Insert(int x, int k)
64
{
65
    DNode y = Split(root, k);
66
    Node *n = new Node(x);
67
    root = Merge(y.first, Merge(n, y.second));
68
}
69
int Ind = 0;
70
int a[100005];
71
void DFS(Node *rt)
72
{
73
    if (rt)
74
    {
75
        DFS(rt->ch[0]);
76
        a[rt->id] = ++Ind;
77
        DFS(rt->ch[1]);
78
    }
79
}
80
int main()
81
{
82
    int n;
83
    scanf("%d", &n);
84
    int c;
85
    Insert(1, 0);
86
    for (int i = 2; i <= n; i++)
87
    {
88
        scanf("%d", &c);
89
        Insert(i, c);
90
    }
91
    DFS(root);
92
    for (int i = 1; i <= n; i++)
93
    {
94
        printf("%d\n", a[i]);
95
    }
96
    //while(1);
97
}