coreBugZJ

reverse order 1，HUST Monthly 2011.04.09 之 C，1433

Description

Here is a sequence a_1..n, which is a disordered sequence from 1 to N. If i < j and a_i > a_j, then <i, j> is called a pair of inversion. And b_1..n-1 is defined as follows, b_k 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.

Sample Input

5
3 1 4 2 5

Sample Output

2 1 2 0

樹狀數組。。。

 1#include <iostream>
 2
 3using namespace std;
 4
 5typedef  long long  Lint;
 6
 7const int L = 200009;
 8
 9int n, a[ L ];
10Lint b[ L ], al[ L ], sl[ L ], ar[ L ], sr[ L ];
11
12void 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
21void 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
29Lint 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
38int 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], 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 閱讀(924) 評論(0)  編輯 收藏 引用 所屬分類: ACM