（树状数组）POJ

原题链接：http://poj.org/problem?id=2299

---

题意：求冒泡排序交换数字的次数

---

分析：起初听别人说挑战上的冒泡排序交换次数，一直是一头雾水。某天仔细想想，瞬间懂了。

其实就是把给数列按照给你的顺序插入到另一个数组中，插入的位置就是这个数在已经排好序的情况下所在的位置。所以前面的都是比它小，后面的都比它大。

通过很便捷的计算就能算出答案。

for (int j = 0; j < n; j++)[
    ans += j - sum(a[j]);
    add(a[j], 1);
]

sum(a[j])就是<=a[j]的已经插入的数的个数，j-sum(a[j])就是>a[j]的个数。

但是本题999999999过大，需要离散化。

---

代码：

const int maxn = 500010;
int bit[maxn];
struct Num {
    int val;
    int pos;
    bool operator <(const Num &a)const {
        return val < a.val;
    }
}num[maxn];
int n;

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

int sum(int i) {
    int res = 0;
    while (i > 0) {
        res += bit[i];
        i -= lowbit(i);
    }
    return res;
}

void add(int i, int x) {
    while (i <= n) {
        bit[i] += x;
        i += lowbit(i);
    }
}




void solve() {
    while (cin >> n&&n) {
        memset(bit, 0, sizeof(bit));
        ll ans = 0;
        for (int i = 0; i < n; i++) {
            cin >> num[i].val;
            num[i].pos = i;
        }
        sort(num, num + n);
        for (int i = 0; i < n; i++) {
            int tmp = sum(num[i].pos + 1);
            cout << tmp << endl << endl;
            ans += i - tmp;
            add(num[i].pos + 1, 1);
        }
        cout << ans << endl;
    }
}