树状数组模板

树状数组：

//模板是求数组中的逆序对数 typedef long long ll; const int N = 500000 + 10; int a[N], b[N]; struct Bit //封装成结构体更好看些。 { int n, b[N]; void init(int _n) { n = _n; memset(b, 0, sizeof b); } void add(int i, int x) { for(; i <= n; i += i & -i) b[i] += x; } int sum(int i) { int ans = 0; for(; i >= 1; i -= i & -i) ans += b[i]; return ans; } }bit; int main() { int n; while(~scanf("%d", &n)) { for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i]; sort(b + 1, b + 1 + n); int k = unique(b + 1, b + 1 + n) - b - 1; bit.init(k); ll ans = 0; for(int i = 1; i <= n; i++) { a[i] = lower_bound(b+1, b+1+k, a[i]) - b; ans += i-1 - bit.sum(a[i]);//若无逆序，前面应该出现i-1个数字，未在前面出现的即是逆序数 bit.add(a[i], 1); } printf("%lld\n", ans); } return 0; }