2275.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 66 行

/*  This Code is Submitted by wywcgs for Problem 2275 on 2006-06-11 at 19:15:51 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MN = 51200;
const int AN = 33000;

class TreeArray {
public:
	int B[AN];
	int lowBit(int) const;
	void clear();
	void add(int, int);
	int sum(int) const;
};
void TreeArray::clear() {
	memset(B, 0, sizeof(B));
}
int TreeArray::lowBit(int t) const { 
	return t & (-t); 
}
void TreeArray::add(int n, int m) { 
	while(n < AN) { 
		B[n] += m; 
		n += lowBit(n); 
	}
}
int TreeArray::sum(int n) const { 
	int p = 0; 
	while(n > 0) { 
		p += B[n]; 
		n -= lowBit(n); 
	} 
	return p; 
}

int main()
{
	int num[MN], n, i;
	int ln[MN], rn[MN];
	TreeArray ta;
	
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) {
			scanf("%d", &num[i]);
			num[i]++;
		}
		ta.clear();
		for(i = 0; i < n; i++) {
			ta.add(num[i], 1);
			ln[i] = ta.sum(num[i]-1);
		}
		ta.clear();
		for(i = n-1; i >= 0; i--) {
			ta.add(num[i], 1);
			rn[i] = ta.sum(num[i]-1);
		}
		long long sn = 0;
		for(i = 0; i < n; i++) sn += ln[i] * rn[i];
		printf("%lld\n", sn);
	}
	
	return 0;
}