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を2点で探すことができ,複雑度は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
",b[i]);

    }

    return 0;

}