POI 2 Stage 3 Coding of Permutations ( Fenwick Tree, Binary Search )

http://main.edu.pl/en/archive/oi/2/kod

題意：
給一個序列 B，問是否有一個 [ 1, | B | ] 的排列 A，使得 B[ i ] 等於 A[ 0, i ) 中比 A[ i ] 大的數字的數量。輸出方案。

資料規模：
In the first line of the standard input there is a positive integer 30000. It is the number of elements of the sequence B.
In each of the following lines there is one nonnegative integer not greater than 30000. It is the successive element of the sequence B.

解法：
從右邊構造，可以發現總是可以唯一確定要用的數字，A[ i ] 一定是右邊沒有用的數字裡第 i - B[ i ] 小的。
因此只要用支持修改和詢問第 k 小的結構即可，這裡用 fenwick tree。

時間 / 空間複雜度：
O( N lg N ) / O( N )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30000;

int N;
int B[ MAXN + 1 ];
int A[ MAXN + 1 ];

int ftree[ MAXN + 1 ];

void add( int x, int v ){
  for( int i = x; i <= N; i += i & -i ){
    ftree[ i ] += v;
  }
}

int kth( int v ){
  int x = 0;
  for( int i = 1 << 31 - __builtin_clz( N ); i; i >>= 1 ){
    if( x + i <= N and ftree[ x + i ] < v ){
      v -= ftree[ x + i ];
      x += i;
    }
  }
  return x + 1;
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 1; i <= N; ++i ){
    cin >> B[ i ];
    add( i, 1 );
  }
  for( int i = N; i >= 1; --i ){
    if( B[ i ] >= i ){
      cout << "NIE\n";
      exit( 0 );
    }
    A[ i ] = kth( i - B[ i ] ); // 1 base kth smallest
    add( A[ i ], -1 );
  }
  for( int i = 1; i <= N; ++i ){
    cout << A[ i ] << "\n";
  }
  return 0;
}