逆序数
1.定义
在⼀个排列中，如果⼀对数的前后位置与⼤⼩顺序相反，即前⾯的数⼤于后⾯的数，那么它们就称为⼀个逆序。⼀个排列中逆序的总数就称为这个排列的逆序数。
举个例⼦：
标准列是1 2 3 4 5
那么 5 4 3 2 1 的逆序数算法：
看第⼆个，4之前有⼀个5，在标准列中5在4的后⾯，所以记1个类似的，
第三个 3 之前有 4 5 都是在标准列中3的后⾯，所以记2个同样的，
2 之前有3个，
1之前有4个
将这些数加起来就是逆序数=1+2+3+4=10
再举⼀个 2 4 3 1 5
4 之前有0个
3 之前有1个
1 之前有3个
5 之前有0个
所以逆序数就是1+3=4
2.求法
1.朴素⽅法，两层循环，时间复杂度（O (n^2)）
1int count=0;
2for(i=0; i<n-1; i++)
3 {
4for(j=i+1; j<n; j++)
5    {
6if(a[i]>a[j])
7        {
8            count++;
9        }
10    }
11 }
2.归并排序，时间复杂度（O(n log n)）
归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进⾏归并排序，然后再将这两半合并起来。在合并的过程中（设
l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产⽣逆序数；当a[i]>a[j]时，在前半部分中⽐a[i]⼤的数都⽐a[j]⼤，将a[j]放在a[i]前⾯的话，逆序数要加上mid+1-i。因此，可以在归并排序中的合并过程中计算逆序数.
现在以6 1 7 2为例，我们以7 2这⼀块来说，归并排序中当7进⼊临时空间的时候，看看6 1这⼀块还剩下⼏个元素没有⼊临时空间，剩下的元素必定⽐7⼤，剩下的元素个数就是由于7产⽣的逆序对数⽬，同样地1产⽣的逆序对数⽬类似统计，同样，由于不同块之间互不影响，递归解决此问题。说的有点乱，但仔细想想是这个道理
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4#define maxn 500010
5#define ll long long int
6using namespace std;
cstring转为int7 ll a[maxn];
8 ll temp[maxn];
9 ll sum;
10void Merge(int l,int r,int m)
11 {
12int i=l;
13int j = m + 1;
14int k = l;
15while(i<=m&&j<=r)
16    {
17if(a[i]>a[j])
18        {
19            sum+=m-i+1;///剩下的没有进⼊临时空间的元素的个数
20            temp[k++]=a[j++];
21        }
22else
23        {
24            temp[k++]=a[i++];
25        }
26    }
27while(i<=m)///将剩余的元素存到数组中
28    {
29        temp[k++]=a[i++];
30    }
31while(j<=r)
32    {
33        temp[k++]=a[j++];
34    }
35for(i=l; i<=r; i++)
36    {
37        a[i]=temp[i];
38    }
39 }
40void mergesort(int l,int r)
41 {
42if(l<r)
43    {
44int m = (l + r) / 2;
45        mergesort(l,m);///左⼆分排序
46        mergesort(m+1,r);///右⼆分排序
47        Merge(l,r,m);///合并两个升序数组
48    }
49 }
50int main()
51 {
52int n,i;
53while(scanf("%d",&n)!=EOF)
54    {
55if(n==0)
56        {
57break;
58        }
59for(i=0; i<n; i++)
60        {
61            scanf("%lld",&a[i]);
62        }
63        sum=0;
64        mergesort(0,n-1);
65        printf("%lld ",sum);
66    }
67return0;
68 }
3.树状数组
由于树状数组的特性，求和是从当前节点往前求，所以，这⾥要查询插⼊当前数值之时，要统计有多少个⼩于该数值的数还没插⼊，这些没插⼊的数，都会在后⾯插⼊，也就形成了逆序数。
假设我们将序列 6 1 2 7 3 4 8 5 存⼊数组a【】中， a【1】=6 ， a【2】=1...
那么每次，我们可以将 a【i】插⼊到树状数组中，并赋值为 1，我们求和sum，sum 是1 到 a【i】的和，那么这个 sum 表⽰的值就是当前⽐a【i】⼩的数量（包括它本⾝）；⽽当前⼀共有 i 个数，所以当前⽐a【i】⼤的数量就是 i - sum；所以我们统计所有的 i - sum ，它们的和就是逆序数。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5using namespace std;
6#define LL long long
7#define N 1005*1005
8 LL ans;
9int a[N];
10int n,c[N];
11int lowbit(int x)
12 {
13return x&-x;
14 }
15int Getsum(int x)
16 {
17int ret = 0;
18while(x>0)
19    {
20        ret+=c[x];
21        x-=lowbit(x);
22    }
23return ret;
24 }
25
26void add(int x,int d)
27 {
28while(x<=n)
29    {
30        c[x]+=d;
31        x+=lowbit(x);
32    }
33 }
34int main()
35 {
36int i,j,k,l,r,t;
37    scanf("%d",&n);
38    memset(c,0,sizeof(c));
39for(i = 1; i<=n; i++)
40    {
41        scanf("%d",&a[i]);
42    }
43    ans = 0;
44for(i = 1; i<=n; i++)
45    {
46        add(a[i],1);///这⾥将从c[i]赋值为1更像是⼀种存在，1代表着存在，0不存在
47        ans+=i-Getsum(a[i]);
48    }
49    printf("%lld\n",ans);
50return0;
51 }
4.线段树
⽤线段树来求逆序数的思路关键在于，线段树是维护⼀个区间的，所以，对于这种连续区间求逆序数，
完全可以判断当插⼊⼀个新的数字时，若⽐它⼤的数字已经插⼊了，说明排在了它的前⾯，也就是产⽣了这些逆序数。其实线段树与树状数组只是两种不同的数据结构，但在逆序对的处理上⼆者其实是相同的，树状数组有Getsum（）函数求1 到 a【i】的和，⽽线段树则可以使⽤Query（）来查询。
1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4#define MAX 51000
5#define MID(a,b) (a+b)>>1
6#define R(a) (a<<1|1)
7#define L(a) a<<1
8 typedef struct
9 {
10int num,left,right;
11 } Node;
12int ans[MAX];
13 Node Tree[MAX<<2];
14int n;
15void Build(int t,int l,int r)        //以1为根节点建⽴线段树
16 {
17int mid;
18    Tree[t].left=l,Tree[t].right=r;
19if(Tree[t].left==Tree[t].right)
20    {
21        Tree[t].num=0;
22return ;
23    }
24    mid=MID(Tree[t].left,Tree[t].right);
25    Build(L(t),l,mid);
26    Build(R(t),mid+1,r);
27 }
28
29void Insert(int t,int l,int r,int x)    //向以1为根节点的区间[l,r]插⼊数字1
30 {
31int mid;
32if(Tree[t].left==l&&Tree[t].right==r)
33    {
34        Tree[t].num+=x;
35return ;
36    }
37    mid=MID(Tree[t].left,Tree[t].right);
38if(l>mid)
39    {
40        Insert(R(t),l,r,x);
41    }
42else if(r<=mid)
43    {
44        Insert(L(t),l,r,x);
45    }
46else
47    {
48        Insert(L(t),l,mid,x);
49        Insert(R(t),mid+1,r,x);
50    }
51    Tree[t].num=Tree[L(t)].num+Tree[R(t)].num;
52 }
53int Query(int t,int l,int r)          //查询以1为根节点，区间[l,r]的和
54 {
55int mid;
56if(Tree[t].left==l&&Tree[t].right==r)
57return Tree[t].num;
58    mid=MID(Tree[t].left,Tree[t].right);
59if(l>mid)
60    {
61return Query(R(t),l,r);
62    }
63else if(r<=mid)
64    {
65return Query(L(t),l,r);
66    }
67else
68    {
69return Query(L(t),l,mid)+Query(R(t),mid+1,r);
70    }
71 }
72int main()
73 {
74int a,n,i,t;
75    scanf("%d",&t);
76long long int k;
77while(t--)
78    {
79        scanf("%d",&n);
80        memset(Tree,0,sizeof(Tree));  //初始化线段树
81        Build(1,1,n);
82for(i=1; i<=n; i++)          //输⼊n个数
83        {
84            scanf("%d",&ans[i]);
85        }
86for(i=1,k=0; i<=n; i++)
87        {
88            a=ans[i];
89            Insert(1,a,a,1);          //把线段树[ans[i],ans[i]]区间的值插⼊为1
90            k=k+(i-Query(1,1,a));    //查询区间[1,ans[i]]值的总和，逆序数等于i-[1,ans[i]]
91        }
92        printf("%lld\n",k);
93    }
94return0;
95 }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。