题意：给一个排列的每个前缀区间的逆序对数，让还原 原序列。
思路：考虑逆序对的意思，对于k = f[i] - f[i -1]，就表示在第i个位置前面有k个比当前位置大的数，那么也就是：除了i后面的数字之外，它是在剩下的数字当中第k+1大的。
知道这个之后，可以用树状数组来帮助找出剩下的数中第k大的数，刚开始我们可以让1～n中每个元素都标记为1,那么他们的前缀和就代表它是第几小。所以，我们可以对于他们的和来二分快速寻找第k大数。其实在树状数组里面是按照第(i-k)小来找的。找完之后要删除这个元素的值。将它标记为0;
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm> using namespace std; const int maxn = ;
int f[maxn];
int c[maxn];
int ans[maxn];
int lowbit(int x)
{
return x & (-x);
}
void add(int pos, int num, int n)
{
while (pos <= n)
{
c[pos] += num;
pos += lowbit(pos);
}
}
int getSum(int pos)
{
int sum = ;
while (pos > )
{
sum += c[pos];
pos -= lowbit(pos);
}
return sum;
}
void init(int n)
{
memset(c, , sizeof(c));
for (int i = ; i <= n; i++)
add(i, , n);
}
int search(int k, int n)
{
int l = , r = n, mid;
while (l <= r)
{
mid = (l + r) / ;
int sum = getSum(mid);
if (sum >= k) r = mid - ;
else l = mid + ;
}
return l;
}
int main()
{
int T, n;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
init(n);
for (int i = ; i <= n; i++)
scanf("%d", &f[i]);
for (int i = n; i >= ; i--)
{
int k = f[i] - f[i - ];//第k+1大
k = i - k;//在剩下的里面第i - k 小
int pos = search(k, n);//二分找出第k小的位置
ans[i] = pos;
add(pos, -, n);
}
for (int i = ; i < n; i++) printf("%d ", ans[i]);
printf("%d\n", ans[n]);
}
return ;
}