题意：
ZYB有一个排列PP,但他只记得PP中每个前缀区间的逆序对数,现在他要求你还原这个排列. (i,j)(i < j)(i,j)(i<j)被称为一对逆序对当且仅当A_i>A_jAi>Aj
输入描述
第一行一个整数TT表示数据组数。 接下来每组数据： 第一行一个正整数NN,描述排列的长度. 第二行NN个正整数A_iAi,描述前缀区间[1,i][1,i]的逆序对数. 数据保证合法. 1 \leq T \leq 51≤T≤5,1 \leq N \leq 500001≤N≤50000
输出描述
TT行每行NN个整数表示答案的排列.
输入样例
1
3
0 1 2
输出样例
3 1 2
思路：
a[i]表示[1,i]的逆序对，所以a[i] - a[i-1]便是i前面比第i个数大的，所以a[i]-a[i-1]+1便是第i个数在[1,i]中第几大。
所以用树桩数组全部初始化为1，然后二分+树状数组找出第k大的数然后把其赋值为0即可。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
#define N 100050
int a[N];
int ans[N];
int tree[N],dis[N];
int n;
void add(int x,int dx)
{
while(x <= n)
{
tree[x] += dx;
x += x&(-x);
}
} int query(int x)
{
int sum = 0;
while(x)
{
sum += tree[x];
x -= x&(-x);
}
return sum;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n); for(int i = 1; i <= n; i++)
add(i,1); for(int i = 1; i <= n; i++)
scanf("%d",a+i);
for(int i = n; i >= 1; i--)
{
dis[i] = a[i]-a[i-1]+1;
int l = 1,r = n;
int tt;
while(l < r)
{
int mid = (l+r)/2;
if(query(mid) < dis[i])
l = mid+1;
else if(query(mid) > dis[i])
r = mid-1;
else
{
tt = r;
r -= 1;
}
}
ans[i] = r;
add(l,-1);
}
for(int i= 1; i <= n; i++)
printf("%d%c",n+1-ans[i],(i==n)? '\n':' ');
}
}