一天一道算法题——逆序对（归并排序，树状数组，离散化）

题目【逆序对】：https://www.luogu.com.cn/problem/P1908

解法一：暴力法，适用于n比较小的时候，本题不适用。

解法二：归并排序。

我们很容易得出在合并操作的时候会找到逆序对。

记i指向左边区域的当前节点，j指向右边区域的当前节点。

当a[i]<=a[j]时，a[i]与右边区域的大于等于a[j]的所有数不构成逆序对,只需i++就好。

当a[i]>a[j]时，a[j]与左区域的大于等于a[i]的所有数皆构成逆序对，所以逆序对数目+=mid-l+1

因为int会溢出，所以sum用了long long

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #define N 500010
 5 using namespace std;
 6 
 7 int n, a[N],c[N];
 8 long long sum=0;
 9 void mergeSort(int l, int r) {
10     if (l >= r)return;
11     int mid = (l + r) >> 1,k = mid + 1, t = l, left = l, right = r;
12     mergeSort(l, mid);
13     mergeSort(mid + 1, r);
14     while (l <= mid && k <= r) {
15         if (a[l] <= a[k]) {
16             c[t++] = a[l++];
17         }
18         else
19             c[t++] = a[k++], sum += (long long)mid - l + 1;
20     }
21     while (l <= mid)
22         c[t++] = a[l++];
23     while (k <= r)
24         c[t++] = a[k++];
25     for (; left <= right; left++)
26         a[left] = c[left];
27 }
28 
29 int main() {
30     scanf("%d", &n);
31     for (int i = 1; i <= n; i++)
32         scanf("%d", &a[i]);
33     mergeSort(1, n);
34     printf("%lld", sum);
35     return 0;
36 }

∠(°ゝ°)！

解法三：树状数组

记a[i]为原数组

然后我们将每个a[i]在树状数组tree[]里对应的位置都+1，这样a[i]的前缀和就代表了比它小或相等的数，那么i-前缀和就是逆序对的数量了。

接着……溢出了。

因为序列中的每个数不超过10^9，所以，你懂的。

为了减少空间消耗，我们采用离散化。

将a排序，然后将每个数分别用1……n代替，这样tree只需要10^5<<2的大小，大大减少了消耗。

代码如下：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<stdio.h>
 4 #define N 500010
 5 #define lowbit(x) x&-x
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 int n, b[N],tree[N<<2];
10 struct node {
11     int val, num;
12 } a[N];
13 
14 //inline作用和define差不多
15 inline bool cmp(node a, node b) {
16     if (a.val == b.val)return a.num < b.num;
17     return a.val < b.val;
18 }
19 void insert(int x, int k) {
20     while (x <= n) {
21         tree[x] += k;
22         x += lowbit(x);
23     }
24 }
25 ll query(int x) {
26     ll ans = 0;
27     while (x) {
28         ans += tree[x];
29         x -= lowbit(x);
30     }
31     return ans;
32 }
33 
34 int main() {
35     scanf("%d", &n);
36     for (int i = 1; i <= n; i++)
37         scanf("%d", &a[i].val), a[i].num = i;
38     //离散化，防止有些数太大，导出空间溢出
39     sort(a + 1, a + n + 1, cmp);
40     for (int i = 1; i <= n; i++)
41         b[a[i].num] = i;
42     ll ans=0;
43     for (int i = 1; i <= n; i++) {
44         insert(b[i], 1);
45         ans += i-query(b[i]);
46     }
47     printf("%lld", ans);
48     return 0;
49 }