# coreBugZJ

## reverse order 1

Time Limit: 1 Sec Memory Limit: 128 MB
Submissions: 531 Solved: 87

## Description

Here is a sequence a1..n, which is a disordered sequence from 1 to N. If i < j and ai > aj, then <i, j> is called a pair of inversion. And b1..n-1 is defined as follows, bk is the number of the total inversion pairs in array a, when i<=k<j. Now the array b is required while the array a is known.

## Input

Several cases end with the end of the file;

And each of the cases includes two lines, a integer n(2<=n<=10^5)in the first line, and the second line followed with n integer, which is in the presentation of array a;

## Output

Output the answer of each case in a line, namely the array b, and a space is required between the adjacent integers.

```5
3 1 4 2 5```

## Sample Output

`2 1 2 0`
` `
`树状数组。。。`
``` 1 #include <iostream> 2 3 using namespace std; 4 5 typedef  long long  Lint; 6 7 const int L = 200009; 8 9 int n, a[ L ];10 Lint b[ L ], al[ L ], sl[ L ], ar[ L ], sr[ L ];11 12  void init( Lint a[], Lint s[] ) {13 int i;14  for ( i = 0; i <= n; ++i ) {15 a[ i ] = s[ i ] = 0;16 }17 }18 19 #define  getBit(i)  (i&(i^(i-1)))20 21  void add( Lint a[], Lint s[], int i, Lint d ) {22 a[ i ] += d;23  while ( i <= n ) {24 s[ i ] += d;25 i += getBit(i);26 }27 }28 29  Lint get( Lint a[], Lint s[], int i ) {30 Lint res = -a[ i ];31  while ( i > 0 ) {32 res += s[ i ];33 i -= getBit( i );34 }35 return res;36 }37 38  int main() {39 int i;40  while ( cin >> n ) {41  for ( i = 1; i <= n; ++i ) {42 cin >> a[ i ];43 }44 init( al, sl );45 init( ar, sr );46  for ( i = n; i > 0; --i ) {47 add( ar, sr, a[ i ], 1 );48 }49 b[ 1 ] = get( ar, sr, a[ 1 ] );50 add( al, sl, n+1-a, 1 );51  for ( i = 2; i < n; ++i ) {52 add( ar, sr, a[i-1], -1 );53 add( al, sl, n+1-a[i], 1 );54 b[ i ] = b[ i - 1 ] - get( al, sl, n+1-a[i] ) + get( ar, sr, a[i] );55 }56 cout << b[ 1 ];57  for ( i = 2; i < n; ++i ) {58 cout << " " << b[ i ];59 }60 cout << "\n";61 }62 return 0;63 }64 ```

posted on 2011-04-09 18:35 coreBugZJ 阅读(818) 评论(0)  编辑 收藏 引用 所属分类: ACM 