HDU 3743 Frosh Week(樹狀數組求逆序數)

模闆題，有一個坑點，學生編号并不一定是老老實實的1、2、3、.....n這個排列，可能很大，是以一開始RE了。    給編号另配置設定一個編号，隻要滿足大小關系就行。

細節參見代碼：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<list>
#include<cmath>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 1000000+10;
int T,n,a[maxn],x,y,bit[maxn],id[maxn];
int sum(int x) {
    int ret = 0;
    while(x > 0) {
        ret += bit[x]; x -= (x & -x);
    }
    return ret;
}
void add(int x,int d) {
    while(x <= n) {
        bit[x] += d; x += (x & -x);
    }
}
int main() {
    while(~scanf("%d",&n)) {
        memset(bit,0,sizeof(bit));
        for(int i=0;i<n;i++) scanf("%d",&a[i]), id[i] = a[i];
        sort(id,id+n);
        for(int i=0;i<n;i++) {
            int v = lower_bound(id,id+n,a[i]) - id + 1;
            a[i] = v;
        }
        ll ans = 0;
        for(int i=0;i<n;i++) {
            ans += (i - sum(a[i]));
            add(a[i], 1);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}