SPOJ227 Ordering the Soldiers

题目大意

给定一个序列a[1],a[2],a[3]…..a[n]，a[i]表示位置i之前有a[i]个数比位置i上的数字大，要求你求出每一个位置上的具体数字

题解

直接上网上的题解吧。。。

这题与正常的树状数组题目正好想反，给定数组b[i]表示i前面比a[i]大的点的个数，求a[]数组。
我们可以先想想朴素的做法，比如b[] = {0, 1, 2, 0, 1}，我们用数组c[i]表示还存在的小于等于i的个数，一开始c[] = {1, 2, 3, 4, 5}，下标从1开始。
     我们从右向左扫描b[]数组，b[5] = 1，说明该点的数是剩下的数中第4大的，也就是小于等于它的有4个，即我们要找最小的j符合c[j] = 4(这里可以想想为什么是最小的，不是最大的，挺好理解的)，而c[]是有序的，所以可以用二分来找j，复杂度为O(logn)，但现在问题是每次更新c[]要O(n)的复杂度，这里我们就想到树状数组，c[i]表示还存在的小于等于i的个数，这不正好是树状数组的看家本领吗～～所以处理每个位置的复杂度为O(logn * logn)，总的复杂度为O(n * logn * logn)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 200005
using namespace std;
int a[MAXN],b[MAXN],c[MAXN];
int n;
int lowbit(int x)
{
    return x&-x;
}
int sum(int x)
{
    int ret=0;
    while(x>0)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}
void add(int x,int d)
{
    while(x<=n)
    {
        c[x]+=d;
        x+=lowbit(x);
    }
}
int main(void)
{
    int T,i,l,r,t,m;
    cin>>T;
    while(T--)
    {
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        scanf("%d",&n);
        for(i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            add(i,1);
        }
        for(i=n; i>=1; i--)
        {
            t=i-a[i];
            l=1;
            r=n;
            while(l<=r)
            {
                m=(l+r)/2;
                if(sum(m)>=t)
                    r=m-1;
                else
                    l=m+1;
            }
            add(l,-1);
            b[i]=l;
        }
        for(i=1; i<n; i++)
            printf("%d ",b[i]);
        printf("%d\n",b[i]);
    }
    return 0;
}