Lost Cows（树状数组）

试题链接

题意：

求出一个１到ｎ的排列，这个排列只告诉了你从第二个数字开始的比这个数字小的数的个数。

题解：

如果一个数p，p的前面有m个比他小的数，后面有n个比他小的数，那p的位置就是n+m+1
我们可以二分这个p，如果m+n+1>mid,mid就取小了；否则就取大了
p前面有多少比他小的数，在输入答案时就知道了
p后面有多少比他小的数，可以用树状数组来搞定
我们在处理时应该倒序处理，想想最后一个数的真实值就是a[n]+1,然后删除最后一个数，看倒数第二个，一次类推即可

代码：

# include<cstdio>
# include<iostream>
# include<fstream>
# include<algorithm>
# include<functional>
# include<cstring>
# include<string>
# include<cstdlib>
# include<iomanip>
# include<numeric>
# include<cctype>
# include<cmath>
# include<ctime>
# include<queue>
# include<stack>
# include<list>
# include<set>
# include<map>

using namespace std;

const double PI=4.0*atan(1.0);

typedef long long LL;
typedef unsigned long long ULL;

# define inf 999999999
# define MAX 8000+4

int a[MAX];
int ans[MAX];
int tree[MAX];

int n;
int lowbit(int x)
{
    return x&(-x);
}
int getsum ( int pos )//后面比他小的数字的个数 
{
    int ans = 0;
    while ( pos > 0 )
    {
        ans+=tree[pos];
        pos-=lowbit(pos);
    }
    return ans;
}

void update ( int pos,int val )
{
    while ( pos <= n )
    {
        tree[pos]+=val;
        pos+=lowbit(pos);
    }
}

int my_search ( int k )
{
    int left = 1, right = n;
    while ( left < right )
    {
        int mid = ( left+right )>>1;
        int num = getsum (mid);
        if ( mid - 1 < num+k )
        {
            left = mid+1;
        }
        else
        {
            right = mid;
        }
    }
    return left;
}

int main(void)
{
    while ( scanf("%d",&n)!=EOF )
    {
        memset(tree,0,sizeof(tree));
        memset(ans,0,sizeof(ans));
        a[1] = 0;
        for ( int i = 2;i <= n;i++ )
            scanf("%d",&a[i]);
        for ( int i = n;i >= 1;i-- )
        {
            int k = my_search(a[i]);
            update(k,1);//每确定一个位置，进行更新 
            ans[i] = k;
        }

        for ( int i = 1;i <= n;i++ )
            printf("%d\n",ans[i]);
    }



    return 0;
}