​ 先从简单的情况开始讨论。例如： $1 2 3 5 4$ 。显然该数列对应的逆序数数列为 $0 0 0 0 1$ 。我们可以从后往前进行还原：对于最后一个数，前面仅有一个数字比它大，所以为 $n-1 = 4$ ；接着倒数第二个数，没有比它大的，所以是剩余的数字中最大的那个，即 $5$ ；对于倒数第三个数，同理，而由于 $4 5$ 已被使用，故此处为 $3$ ...可以发现，当原数列中该数对应逆序数为 $i$ ，这个数就是剩余的数字中第 $i+1$ 大的数。

​ 那么，问题是，我们怎么知道哪些数字已经没有了呢？或者说，我们是否可以知道，对于第 $i (1 \leq i \leq n)$ 个数，比它大的数字已经用过了多少呢？

​ 对于上述例子，它的复原我们可以换一种视角看待：对于最后一个数，仍然以 $n-1 = 4$ 得到；得到该数后，我们可以维护一个 $used$ 数组，代表大于等于他的数字有多少个已经被使用过；同时设置一个 $prev$ （初值为0），代表上一个数 $x$ 的 $used[x]$ 的值。在此，我们可以知道该数组应当被更新为 $1 1 1 1 0$ ；接下来，倒数第二个数为 $n-0 = n$ ，发现减数与 $prev$ 相等，不再操作，该数即为 $5$ ，更新数组后，得到 $2 2 2 2 1$ 。倒数第三个数，首先计算 $n-0-1(used$ 数组 $) = 4$ 发现 $used[4] != prev$ ，说明在该数之前已经有别的数字被使用，这个数字不是剩余数字的倒数第二位，还要往前推 $used[4]-prev$ 位。反复执行这一过程，就能得到 $3$ ，向前类似。

​ 然而，以上算法的问题是，每次更新数组的复杂度过高，会导致超时。此时，我们需要结合线段树，利用其 $lazy$ 标记降低复杂度，将复杂度从 $O(n)$ 降低到 $O(logn)$ 。

Code

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int cnt,lazy;
    int l_idx,r_idx;
    Node *l,*r;
    Node()
    {
        cnt=0,lazy=0,l_idx=0,r_idx=0;
        l=NULL,r=NULL;
    }
};

class Tree{
public:
    Node *root;
    void Generate(Node *p,int l0,int r0)
    {
        p->l_idx=l0,p->r_idx=r0;
        if(l0==r0) return;
        p->l=new Node,p->r=new Node;
        int mid=(l0+r0)/2;
        Generate(p->l,l0,mid);
        Generate(p->r,mid+1,r0);
    }
    int Search(Node *p,int idx)
    {
        int mid=(p->l_idx+p->r_idx)/2;
        p->cnt+=p->lazy;
        if(p->l) p->l->lazy+=p->lazy;
        if(p->r) p->r->lazy+=p->lazy;
        p->lazy=0;
        if(p->l_idx==p->r_idx&&p->l_idx==idx) return p->cnt;
        if(idx<=mid) return Search(p->l,idx);
        return Search(p->r,idx);
    }
    void Update(Node *p,int l,int r)
    {
        if(l==p->l_idx&&r==p->r_idx)
        {
            p->lazy++;
            return;
        }
        p->cnt+=p->lazy+1;
        if(p->l) p->l->lazy+=p->lazy;
        if(p->r) p->r->lazy+=p->lazy;
        p->lazy=0;
        int mid=(p->l_idx+p->r_idx)/2;
        if(r<=mid) Update(p->l,l,r);
        else Update(p->l,l,mid),Update(p->r,mid+1,r);
    }
    void Delete(Node *p)
    {
        if(p->l) Delete(p->l);
        if(p->r) Delete(p->r);
        delete p;
    }
    ~Tree()
    {
        Delete(root);
    }
};

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    int s[n];
    for(int i=0;i<n;i++) cin>>s[i];
    for(int i=0;i<n;i++)
        if(s[i]>i)
        {
            cout<<-1;
            return 0;
        }
    vector<int> res;
    Tree t;
    t.root=new Node;
    t.Generate(t.root,1,n);
    // int a[n];
    // for(int i=0;i<n;i++) a[i]=0;
    for(int i=n-1;i>=0;i--)
    {
        int x=n,dif=s[i];
        //int prev=a[n-1];
        int prev=t.Search(t.root,n);
        //x-=dif+a[n-1];
        x-=dif+prev;
        //while(a[x-1]!=prev)
        while(1)
        {
            int temp=prev,v=t.Search(t.root,x);
            if(v==prev) break;
            //prev=a[x-1];
            prev=v;
            //x-=a[x-1]-temp;
            x-=v-temp;
        }
        //for(int j=0;j<x;j++) a[j]++;
        t.Update(t.root,1,x);
        res.push_back(x);
    }
    for(int i=res.size()-1;i>=0;i--) cout<<res[i]<<" ";
    return 0;
}

​