hdu 5592 BestCoder Round #65（树状数组）

题意：

 

$ZYB$有一个排列$P$,但他只记得$P$中每个前缀区间的逆序对数,现在他要求你还原这个排列.

$(i,j)(i<j)$被称为一对逆序对当且仅当A_i>A_jA​i​​>A​j​​

输入描述

第一行一个整数$T$表示数据组数。

接下来每组数据：

第一行一个正整数$N$,描述排列的长度.

第二行$N$个正整数A_iA​i​​,描述前缀区间$[1,i]$的逆序对数.

数据保证合法.

$1\le T\le 5$,$1\le N\le 50000$

输出描述

$T$行每行$N$个整数表示答案的排列.

输入样例

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':' ');
    }
}