题意:给出序列前k项中的逆序对数,构造出这个序列.

分析:使用权值线段树来确定序列元素.

逆序对的数量肯定是递增的,从最后一个元素开始逆向统计,则\(a[i] - a[i-1]\)即位置i之前比位置i上的数大的个数.则该位置的数应该是序列中第\(i-a[i]+a[i-1]\)大的数,通过权值线段树查询全局第k大的数,并将其数量-1.

初始的权值线段树每个值的数量都是1.

#include <bits/stdc++.h>

#define lson rt<<1

#define rson rt<<1|1

#define Lson l,m,lson

#define Rson m+1,r,rson

using namespace std;

typedef long long LL;

const int maxn = 1e5+5;

struct Node{

    int val,num;

}tree[maxn<<2];

void pushup(int rt){

    tree[rt].num = tree[lson].num + tree[rson].num;

}

void build(int l,int r,int rt){

    if(l==r){

        tree[rt].val = l;

        tree[rt].num =1;

        return;

    }

    int m = (l+r)>>1;

    build(Lson);

    build(Rson);

    pushup(rt);

}

int query(int k,int l,int r,int rt){

    if(l==r){

        return tree[rt].val;

    }

    int m = (l+r)>>1;

    if(tree[lson].num>=k) return query(k,Lson);

    else return query(k-tree[lson].num,Rson);

}

void update(int p,int l,int r,int rt){

    if(l==r){

        tree[rt].num --;

        return;

    }

    int m = (l+r)>>1;

    if(p<=m) update(p,Lson);

    else update(p,Rson);

    pushup(rt);

}

int a[maxn];

int ans[maxn];

int main()

{

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    int n,T; scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        for(int i=1;i<=n;++i){

            scanf("%d",&a[i]);

        }

        build(1,n,1);

        for(int i=n;i>=1;--i){

            int del = a[i] - a[i-1];

            ans[i] = query(i-del,1,n,1);

            update(ans[i],1,n,1);

        }

        for(int i=1;i<=n;++i){

            printf("%d%c",ans[i],i==n?'\n':' ');

        }

    }

    return 0;

}