树上神奇 逆 逆序对（我的叫法）hh的小纸条 重中之重！！！！！

HH是一位十分爱好数学的大佬，尤其喜爱数数，一天百无聊赖的他写下了一个1-N的排列，并且在小纸条上记下了每个数前面有多少个数比他小，但HH不小心忘记了这个排列。现在只有当时记下的小纸条，现在请你还原出这个1-N的排列。 

HH:

输入

第一行:一个整数n
接下来n-1行:表示第二个数到第n个数前面有多少个数比它小。 
(因为第一个数前面没有任何数，所以不需要输入)

输出

n行，每行一个整数，表示1个1-n的排列

样例输入 Copy

5
1
2
1
0

样例输出 Copy

2
4
5
3
1
经过长时间的思考（瞎碰），我发现了一件事：
题目翻译成这样：给定每个点的逆序对的数量，求每个点。
我和廖半仙一开始进行了愉快的跳表操作。
事实证明它是完全错的。
总的来说，这题目被坑了的唯一原因就是：


MAXN呐！MAXN呐！
+1=100
-1=60
maxn。。。
ANSWER：
我发现：最后一个值是可以确定的。
因为我们知道最后一个值前面有几个点比它小，于是这个点就是第n+1大的点。
把这个点塞到答案数组里面。
找前一个大小，我们发现：删去第一个点，再进行以上操作，就可以得到这个点的大小。
于是：算法确认：
1、找当前数字对应的第a[n]+1大
2、塞答案
3、删去这个数。
重点来了。
我们删去这个数，怎么实现呢？
如果只要数组硬爆就能解决的事，那还是wzy大佬出的蓝题吗？
不可能！
我需要一个数据结构，来维护这个东西。
想想看数据结构们，有什么可以删点呢？删点之后还要把后面的补上来....
我问到了邻接表删点，甚至想到了主席树删点（区间第k小,动态点删掉然后查询即可）
但是....都不行
平衡树吧，有删点操作。
但是我不会。
感谢shy大佬的shy树。

MAXN呐！MAXN呐！
+1=100
-1=60
maxn。。。

上代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
int n,a[maxn],ans[maxn];
struct tree
{
    int ls,rs,size,pre;
}t[maxn*2];
int tot=0;
int build(int l,int r)
{
    if(l==r)
    {
        t[++tot].size=1;//子树大小，叶节点的子树大小=1
        t[tot].pre=l;//节点的值=l，12345.....
        return tot;//返回当前叶节点的编号
    }
    int mid=(l+r)>>1;
    int x=++tot;//树节点的编号
    t[x].ls=build(l,mid);//同主席树建树模式，ls rs=下面的返回值
    t[x].rs=build(mid+1,r);
    t[x].size=r-l+1;//差分处理子树大小
    return x;
}
int ask(int x,int l,int r,int k)
{
    if(l==r)
    {
        t[x].size--;//叶节点，删除它
        return t[x].pre;//返回叶节点的值
    }
    t[x].size--;//走一条边，删一个点
    int mid=l+r>>1;
    int mik=mid+1;
    int q=k-t[t[x].ls].size;
    if(k<=t[t[x].ls].size)return ask(t[x].ls,l,mid,k);//二叉搜索树部分，有点类似主席树，通过差分不停在节点上滑来滑去，直到找到相应的叶节点
    else                  return ask(t[x].rs,mik,r,q);
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&a[i]);//n-1个
    }
    a[1]=0;//第一个数前面没有比它小的
    build(1,n);//建树
    for(int i=n;i>0;i--)
    {
        ans[i]=ask(1,1,n,a[i]+1);
    }
    for(int i=1;i<=n;i++) printf("%d
",ans[i]);
    return 0;
}

思路就是二叉查找树，建树之后，根据a数组，大了往左找，小了往右找，然后找到这个值为止，删点。

膜拜shy树

%%%shy大佬，tql

（完）