【题意】给定【1,i】前缀逆序对数,还原原序列。
【解题方法】先把前缀和还原成原来的,考虑倒着来,每个就相当于前面有多少个比自己大,线段树求第k大就好了,BIT什么的也可以
【AC 代码】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=50010;
int n,a[maxn];
int sum[maxn<<2],ans[maxn];
void Build(int l,int r,int rt)
{
sum[rt]=r-l+1;
if(l==r) return ;
int mid=(l+r)/2;
Build(l,mid,rt*2);
Build(mid+1,r,rt*2+1);
}
int queryans(int k,int l,int r,int rt)
{
--sum[rt];
if(l==r) return l;
int mid=(l+r)/2;
if(k>=sum[rt*2+1]) return queryans(k-sum[rt*2+1],l,mid,rt*2);
else return queryans(k,mid+1,r,rt*2+1);
}
int main()
{
int 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; i--){
int k=a[i]-a[i-1];
ans[i]=queryans(k,1,n,1);
}
for(int i=1; i<n; i++){
printf("%d ",ans[i]);
}
printf("%d\n",ans[n]);
}
}