逆序对
逆序对非常常见，有三种求解的方法，效率差不多，但是树状数组法较快。
归并排序
归并排序的思想就是递归分治，把要解决的区间分成两个区间比较\(a_i\)和\(a_j\)的大小（其中\(a_i\)属于左区间，\(a_j\)属于右区间，其实就是将左右区间合并、并排序），若\(a_i<a_j\),则将\(a_i\)复制到\(r_k\)中，然后将\(i\)和\(k\)都加\(11\)，否则将\(a_j\)复制到\(r_k\)中，将\(j,k\)加\(11\)，最后再将\(r_k\)移动到\(a_i\)中，然后继续合并；
void msort(int l, int r){ if(l == r) return; int mid = (l + r) / 2; msort(l, mid); msort(mid + 1, r); int i = l; int j = mid + 1; int k = l; while (i <= mid && j <= r) { if (a[i] <= a[j]) { fu[k] = a[i]; k++; i++; } else { fu[k] = a[j]; k++; j++; ans += mid - i + 1; } } while (i <= mid) { fu[k] = a[i]; k++; i++; } while (j <= r) { fu[k] = a[j]; k++; j++; } for (int i = l; i <= r; i++) a[i] = fu[i];} 树状数组
树状数组其实就是桶的思想进行一波优化所得出来的。每拿到一个值放入桶中，统计所有大于这个数的数量，然后累加，发现这正好可以用树状数组优化。当然在使用之前还是应该离散化一下，不然桶会炸的。
#include#include #include #include #define lowbit(n) (n & (-n))#define int long longusing namespace std;int n, sum;int a[1001000], b[1010000], tree[1000100];void add(int x) { while (x <= n) { tree[x]++; x += lowbit(x); }}int query(int x) { int ans = 0; while (x > 0) { ans += tree[x]; x -= lowbit(x); } return ans;}bool cmp(const int &x, const int &y){ if(b[x]==b[y]) return x > y; return b[x] > b[y];}signed main() { scanf("%lld", &n); for(register int i = 1; i <= n; i++) { scanf("%lld", &b[i]); a[i] = i; } sort(a + 1, a + n + 1, cmp); for (int i = 1; i <= n; i++) { add(a[i]); sum += query(a[i] - 1); } printf("%lld", sum);}
线段树
一般的线段树并不能解决这个问题，而且需要用权值线段树来解决这种问题。
#include#include #include #include #define ls left, mid, root << 1#define rs mid + 1, right, root << 1 | 1#define int long longusing namespace std;int data[1010000], ans = 0;struct ha { int num, id;}a[1001000];struct t { int l, r, sum;}tree[2001000];bool cmp(ha a, ha b){ return a.num < b.num;}inline void build(int left, int right, int root){ tree[root].l = left; tree[root].r = right; if (left == right) return; int mid = (left + right) >> 1; build(ls), build(rs);}inline void pushup(int root){ tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum; }void update(int root, int add){ if (tree[root].l == tree[root].r) { tree[root].sum ++; return; } int mid = (tree[root].l + tree[root].r) >> 1; if (add <= mid) update(root << 1, add); else update(root << 1 | 1, add); pushup(root); return;} int query(int root, int a){ if (tree[root].l == tree[root].r) return tree[root].sum; int mid = (tree[root].l + tree[root].r) >> 1; if (a <= mid) return tree[root << 1 | 1].sum + query(root << 1, a); else return query(root << 1 | 1, a);}signed main(){ int n; scanf("%lld", &n); for (int i = 1; i <= n; i++) scanf("%lld", &data[i]), a[i].id = i, a[i].num = data[i]; sort(a + 1, a + 1 + n, cmp);// for (int i = 1, j = 0; i <= n; i++) { if (a[i].num != a[i - 1].num || i == 1) j++; data[a[i].id] = j; } //此处向上为离散化。 build(1, n, 1); for (int i = 1; i <= n; i++) { ans += query(1, data[i] + 1);//要算比data[i]严格大于的数。 update(1, data[i]); } printf("%lld", ans); return 0; }