405 字
2 分钟
Number
题目描述
一个排列,求出了 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 保证解存在
题解
输入的树就是按顺序插入时比他小的数的数量
用一颗平衡树维护就可以了
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
struct Node
{
Node *ch[2];
int s, id, key;
Node(int x)
{
key = rand();
id = x;
s = 1;
ch[0] = ch[1] = NULL;
}
#define size(_) ((_) ? (_)->s : 0)
void Update()
{
s = size(ch[1]) + size(ch[0]) + 1;
}
} * root;
Node *Merge(Node *A, Node *B)
{
if (!A)
return B;
if (!B)
return A;
if (A->key < B->key)
{
A->ch[1] = Merge(A->ch[1], B);
A->Update();
return A;
}
else
{
B->ch[0] = Merge(A, B->ch[0]);
B->Update();
return B;
}
}
typedef pair<Node *, Node *> DNode;
DNode Split(Node *rt, int k)
{
if (!rt)
return DNode(NULL, NULL);
DNode o;
if (size(rt->ch[0]) >= k)
{
o = Split(rt->ch[0], k);
rt->ch[0] = o.second;
rt->Update();
o.second = rt;
}
else
{
o = Split(rt->ch[1], k - size(rt->ch[0]) - 1);
rt->ch[1] = o.first;
rt->Update();
o.first = rt;
}
return o;
}
void Insert(int x, int k)
{
DNode y = Split(root, k);
Node *n = new Node(x);
root = Merge(y.first, Merge(n, y.second));
}
int Ind = 0;
int a[100005];
void DFS(Node *rt)
{
if (rt)
{
DFS(rt->ch[0]);
a[rt->id] = ++Ind;
DFS(rt->ch[1]);
}
}
int main()
{
int n;
scanf("%d", &n);
int c;
Insert(1, 0);
for (int i = 2; i <= n; i++)
{
scanf("%d", &c);
Insert(i, c);
}
DFS(root);
for (int i = 1; i <= n; i++)
{
printf("%d\n", a[i]);
}
//while(1);
}