小朋友排队 （C++代码）

解题思路:
    这道题最终要求解的其实就是给定整数串中的逆序对的个数，但此题直接暴力是会超时的，所以利用树状数组进行求解，思路如下：首先利用输入的整数串构建一个树状数组，然后树状数组的getSum()可以求解从1开始的一些项的和，如果按顺序输入的话，就可以求解当前输入项之前比它矮的小朋友个数，而且也知道已经输入了多少个小朋友的身高，那么很自然可以求出大于等于当前身高的小朋友个数，但是还存在身高相等的情况，需要减去等于当前身高的个数，也就是getSum(i+1)-getSum(i)，存入一个数组，然后，再从尾开始遍历，也可以用同样的方法，求取身高小于当前身高的小朋友个数，然后与之前的大于的对应相加，即可求得对于每一个身高，其逆序对的个数，最后将其全部加起来即是最终结果。
注意事项:
    1. 要注意爆int，对于不高兴度，当交换次数很大的时候是会爆int的。
参考代码:

#include <iostream>
#include <cstring>
#define maxn 100010
#define MAXH 1000010
using namespace std;

long long total[maxn];
int c1[MAXH], c2[MAXH];
int num[maxn];
int cou[MAXH];
int n;

void init() {
	total[0] = 0;
	for (int i = 1; i <= maxn; i++) {
		total[i] = total[i - 1] + i;
	}
}

int lowbit(int x) {
	return x & (-x);
}

void update(int pos, int val, int* c) {
	while (pos <= MAXH) {
		c[pos] += val;
		pos += lowbit(pos);
	}
}

int getSum(int pos, int* c) {
	int ans = 0;
	while (pos > 0) {
		ans += c[pos];
		pos -= lowbit(pos);
	}
	return ans;
}

int main() {

	init();

	while (cin >> n) {
		memset(c1, 0, sizeof(c1));
		memset(c2, 0, sizeof(c2));
		memset(cou, 0, sizeof(cou));

		for (int i = 1; i <= n; i++) {
			cin >> num[i];
			update(num[i] + 1, 1, c1);
			cou[i] = i - getSum(num[i], c1);
			cou[i] -= (getSum(num[i] + 1, c1) - getSum(num[i], c1));
		}

		for (int i = n; i > 0; i--) {
			update(num[i] + 1, 1, c2);
			cou[i] += getSum(num[i], c2);
		}

		long long ans = 0;
		for (int i = 1; i <= n; i++) {
			ans += total[cou[i]];
		}

		cout << ans << endl;
	}

	return 0;
}