题意：

 

ZYB有一个排列PP,但他只记得PP中每个前缀区间的逆序对数,现在他要求你还原这个排列.(i,j)(i < j)(i,j)(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个整数表示答案的排列.

输入样例

130 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 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;#define N 100050int 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':' ');    }}