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.
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
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
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