逆序数的几种求法
转载原地址：https://blog.csdn.net/Du_Mingm/article/details/81203260
首先，逆序数的定义
什么叫逆序数
对于某一个数来说，它的逆序数等于在它之前有多少个比它大的数
对于某一个序列来说，逆序数等于所有数的逆序数之和
例如
序列 5 1 5 2
逆序数 0 1 0 2
序列的逆序数 1+2=3
来看逆序数的求法
方法一
首先将定义一个结构体，存数列的值和下标，然后按数值从大到小（数值相同按下标从大到小）sort一下
然后建立树状数组，从最大的元素开始，将其标记，即 add（p【i】.id，1）
利用其query（i）查询当前1----i的和
对于第i大的数，由于之前所有比它大的数已经标记，所以query（i）就是当前数的逆序数
例如 5 6 3 8 2 其排序之后即是 2 3 5 6 8 将求对应的值的逆序数的问题转化成了求下标对应的逆序数按求逆
1 2 3 4 5 5 3 1 2 4
序数的方法，先求下标的逆序数 即： 0 + 1 + 2 + 2 + 1 = 6 ，答案即是序列的逆序数，
换一种思路来看， 为了避免加入顺序而导致逆序数的不正确，所以从后面开始逆序，因为已经转化成下标的逆序
所以只需看下标即可， 5 3 1 2 4 对于4的逆序只有5，在c[5]+1，
对于2的逆序有5,3，在c[5]+1,c[3]+1
其余类似。。。。。
然后对于3来说的树状数组求1~3的和，即是求以3为逆序数（此例是1,2）的数的个数，
同理对于 i 来求1~i 之间的和，就是来求以 i 为逆序数的数的个数，最后求个总和，也就是所要求的该数列的逆序数。
代码：
#include
#include
#include
using namespace std;
int c[100010];
typedef struct nodee{
int x,num;
}node;
node maze[10010];
bool cmp(node u,node v)
{
if(u.x==v.x)
return u.num>v.num;
return u.x } int lowbit(int x) { return x&(-x); } void add(int x) { while(x<100005){ c[x]+=1; x+=lowbit(x); } } int summ(int x) { int sum=0; while(x>0){ sum+=c[x]; x-=lowbit(x); } return sum; } int main() { int n,i; while(scanf("%d",&n)!=EOF){ memset(c,0,sizeof(c)); for(i=1;i<=n;i++){ scanf("%d",&maze[i].x); maze[i].num=i; } sort(maze+1,maze+n+1,cmp); int sum=0; for(i=n;i>=1;i--){ int y=maze[i].num; sum+=summ(y); add(y); } printf("%d\n",sum); } return 0; } 方法二 也是树状数组，不过要离散化处理 所谓的离散化就是将数组排个序，例如从小到大排序， 那么将第一小记做1，第二小记做2，那么就算是离散化了 （离散，字面意思，分离，散开，分成一个个的小块，当然每个块不能相同） 这个处理的话就是这样 序列 5 1 5 2 离散化数组 3 1 3 2 这样从最小的数开始建立树状数组（标记） 那么i-query（b【i】）就是当前数的逆序数（i为当前第i个的数，b【i】是当前数是第几小， query询问的是1------i有多少个标记的数（小于等于当前数的数），i-query（b【i】）自然是大于当前数 的数 的个数） 例如实例：maze[i].x: 2 5 7 3 4 排序后为 maze[i].x 2 3 4 5 7 maze[i].num 1 2 3 4 5 maze[i].num 1 4 5 2 3 离散化后为： maze[i].x 2 3 4 5 7 按照num的顺序走就是： maze[i].num 1 4 5 2 3 maze[i].num 1 2 3 4 5 b[maze[i].num] 1 2 3 4 5 b[maze[i].num] 1 4 5 2 3 对于这个例子，maze[i].num 从1~n开始遍历，先add(1),改变后缀和，将比1大的c[i]都加1， 然后add(4)，将比4 大的位置都加1 。。。。。以此类推 然后每一次query（b[i]）,就代表在i之前有多少比 b[i] 小的数的个数，因为 i 代表b[i] 的位置，即前面有几个数 所以 i-query(b[i]) ，就代表 b[i] 之前有几个比它大的数的个数。 补充一个 离散化三部曲： 1. 数组 ha[] 存储所有存在过的数据，sort排序 2. 对ha数组进行去重，重复的数据只保留一个。unique去重（unique函数前提有序） 3. 查询某个数字离散化之后对应的数字，lower_bound查排名 代码 #include #include #include #include #define ll long long using namespace std; int n,c[100010]; int lowbit(int x) { return x&(-x); } void add(int k,int num) { while(k<=n) { c[k]+=num; k+=lowbit(k); } } int query(int k) { int sum=0; while(k) { sum+=c[k]; k-=lowbit(k); } return sum; } typedef struct nodee { int x,i; }node; node maze[100010]; bool cmp(node u,node v) { if(u.x==v.x) return u.i>v.i; return u.x } int b[100010]; int main(void) { int i,j,x,y; while(~scanf("%d",&n)) { ll sum = 0; memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { scanf("%d",&maze[i].x); maze[i].i = i; } sort(maze+1,maze+1+n,cmp); int cnt = 1; for(i=1;i<=n;i++){ if(i!=1&&maze[i].x!=maze[i-1].x) cnt++; b[maze[i].i] = cnt; } for(i=1;i<=n;i++) { add(b[i],1); sum += (i-query(b[i])); } printf("%lld\n",sum); } return 0; } 方法三 归并求解（我 还 不 会） 相当漂亮的写法，让我写肯定写不了这么好,但是有个问题是b数组的申请，这里频繁申请爆掉了 我给改成了全局变量 #include using namespace std; long long int cnt; int a[104000]; int *b; void Merge(int a[], int low, int mid, int high); void Merge_sort(int a[], int low, int high);///归并排序 int main(){ int n, i; scanf("%d", &n); for(i = 0; i < n; i++) scanf("%d", &a[i]); b = new int[n]; cnt = 0; Merge_sort(a, 0, n-1); delete[] b; printf("%lld\n", cnt); return 0; } void Merge_sort(int a[], int low, int high){ int mid; if(low < high){ mid = (low + high)/2; Merge_sort(a, low, mid); Merge_sort(a, mid+1, high); Merge(a, low, mid, high); } } void Merge(int a[], int low, int mid, int high){///可类比两组有序链表的归并，思想基本一样 int i = low; int j = mid + 1; int k = 0; //int *b = new int[high-low+1];///动态申请内存 while(i <= mid && j <= high){ if(a[i] <= a[j]) b[k++] = a[i++]; else { b[k++] = a[j++]; cnt += (mid - i + 1);///归并两组有序数据，当a[i] > a[j], 则在区间[i, mid]的数据全部大于a[j],此时对于a[j]的逆序数为(mid - i + 1) } } while(i <= mid){ b[k++] = a[i++]; } while(j <= high){ b[k++] = a[j++]; } for(k = 0, i = low; i <= high; i++, k++){ a[i] = b[k]; } } 方法四 直接数 的就不写了