我们对于每一个数字，记录他之前比他小的数的个数，他之后，比他小的数的个数，然后乘积就是这个数字为中间元素的 所求序列的个数，求和就是所有的了。

用两个树状数组，或者用两次。

#include <cstdio>

#include <cstring>

const int M = 50009;

int d[M], c[M], a[M], b[M], n;

inline int lowbit(int i) {

return i & (-i);

}

void Modify(int i, int m) {

while ( i <= 32768 ) {

c[i] += m;

i += lowbit(i);

}

}

int Sum(int i) {

int ret = 0;

while ( i > 0 ) {

ret += c[i];

i -= lowbit(i);

}

return ret;

}

int main () {

int i, j;

long long ans;

while ( scanf("%d", &n) != EOF ) {

memset(c, 0, sizeof(c) );

for ( i = 0; i < n; i++ ) {

scanf("%d", &d[i]);

a[i] = Sum( d[i] );

/////////////////////////////////////////////////////////////////////////////////////////////////////

对于得到的d[i]序列，比如为5 9 1 8，将这些数字本身当做树状数组的编号。即重新按照大小顺序重新排列了一下，即树状数组是这样的:c[x] 表示大小为x的数是否存在

（这里也可以考虑一下离散化一下） 同时i遍历的顺序是从小变大，保证sum求和的时候求的都是前面的，而不是后面的。这样才能保证树状数组sum(x)统计前面的数字都是比它小的数。大小为d[x]的数字加进来之后，d[x]+1以及后面的数字，比他们小的、在他们之前的数字又多了一个

/////////////////////////////////////////////////////////////////////////////////////////////////////

Modify( d[i] + 1, 1 );

}

memset(c, 0, sizeof(c) );

//树状数组清空，从后向前

for ( i = n - 1; i >= 0; i-- ) {

b[i] = Sum(d[i]);

Modify(d[i] + 1, 1 );

}

// for ( i = 0; i < n; i++ ) {

// printf("%d ", a[i]);

// }

// printf("\n");

// for ( i = 0; i < n; i++ ) {

// printf("%d ", b[i]);

// }

// printf("\n\n");

ans = 0;

for ( i = 0; i < n; i++ )

ans += (long long)a[i] * (long long)b[i];

printf("%lld\n", ans);

}

}

/*

5

1 1 1 1 1

5

0 2 0 2 0

*/

TreeArray_hoj2275