求逆序对

1.

void merge_sort(int l, int r) { if(l == r) return; int mid = (l + r) / 2; merge_sort(l, mid); merge_sort(mid + 1, r); int i = l, j = mid + 1; int tem[MAXN], len = l; while(i <= mid && j <= r) { if(a[i] <= a[j]) { tem[len++] = a[i++]; } else { tem[len++] = a[j++]; ans += mid - i + 1; } } while(i <= mid) tem[len++] = a[i++]; while(j <= r) tem[len++] = a[j++]; for(int i = l; i <= r; i++) a[i] = tem[i]; return; }

2.

#include <iostream> #include <algorithm> using namespace std; const int MAXN = 1005; int n; int rev[MAXN], a[MAXN], BIT[MAXN]; int lowbit(int x) {return x & -x;} void _Update(int, int); int _Sum(int); int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i], rev[i] = a[i]; sort(rev + 1, rev + 1 + n); int len = unique(rev + 1, rev + 1 + n) - rev - 1; for(int i = 1; i <= n; i++) { a[i] = lower_bound(rev + 1, rev + 1 + len, a[i]) - rev; } //离散化 int ans = 0; for(int i = 1; i <= n; i++) { _Update(a[i], 1); ans += i - _Sum(a[i]); } cout << ans; return 0; } void _Update(int index, int x) { for(int i = index; i <= n; i += lowbit(i)) BIT[i] += x; return; } int _Sum(int index) { int sum = 0; for(int i = index; i > 0; i -= lowbit(i)) sum += BIT[i]; return sum; }