[分治与数据结构]逆序对

题目描述

设A[1..n]是一个包含N个数的数组。如果在i〈 j的情况下，有A[i] 〉a[j]，则(i,j)就称为A中的一个逆序对。例如，数组（3，1，4，5，2）的“逆序对”有＜3,1＞,＜3,2＞,＜4,2＞,＜<5,2＞共4个。使用归并排序可以用O(nlogn)的时间解决统计逆序对个数的问题。

输入

第1行：1个整数N表示排序元素的个数。(1≤N≤100000) 第2行：N个用空格分开的整数，每个数在小于100000

输出

1行：仅一个数，即序列中包含的逆序对的个数

样例输入

3
1 3 2

样例输出

解题思路

方法1.分治

归并排序求逆序对，典型的分治，诠释了分而治之。首先将原数列进行递归分解，分解到1个的时候，我们便可以返回进行合并操作了，合并所构成的数列我们可以保证是一定有序的（从大到小或从小到大）。

所以在合并时我们如果发现有与i与j（j>i&&a[i]>a[j]）一对逆序对那么i所在序列的后面的那一些数肯定也会与j成为逆序对

于是这题的方法就出来了，~~表示这就是归并的板题~~。操作大致如图

代码如下

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#define max(a,b) a > b ? a : b
using namespace std;
int n,a[100005],b[100005];
long long ans;
void msort(int l,int r){
    if (l >= r)
        return ;
    int mid = (l + r ) / 2;
    msort (l,mid);
    msort(mid + 1 ,r);
    int x = l,y = mid + 1,k = l;
    while (x <= mid && y <= r){
        if (a[x] > a[y]){
            b[k ++]  = a[y ++];
            ans += mid - x+1;
        }
        else
            b[k ++ ] = a[x ++];
    }
    while (x <= mid )
        b[k ++ ] = a[x ++];
    while (y <= r)
        b[k ++ ] = a[y ++];
    for (int i = l; i <= r ;i ++ )
        a[i] = b[i];
}
int main(){
    scanf ("%d",&n);
    for (int i = 1;i <= n; i ++ ){
        scanf ("%d",&a[i]);
    }
    msort(1,n);
    printf ("%lld",ans);
}

方法2.树状数组

先说说树状数组的一系列定义吧

树状数组(Binary Indexed Tree(B.I.T)也称作Fenwick Tree)是一个区间查询和单点修改复杂度都为log(n)的数据结构。主要用于查询任意两点之间的所有元素之和树状数组(Binary Indexed Tree(B.I.T)

首先先给一个简易树状数组的图，顺便看看它是怎么生成的

由图，我们可以看出树状数组使用二进制数所形成的。c[i]表示i所拥有的子节点所对应的数之和，但如何确定i有几个子节点呢，应该累加那些呢？~~所以有了构造树状数组近乎模板的东西。~~

这里就介绍一下lowbit

lowbit(i)的意思是将 i 转化成二进制数之后，只保留最低位的1及其后面的0，截断前面的内容，然后再转成十进制数，这个数也是树状数组中i号位的子叶个数。

例如：lowbit（22）22的二进制数为10110，进行lowbit操作后，就成了这一个二进制编码便成了10再转换成十进制数，就是2，也就是说22的子节点总数只有2，c[22]=a[21]+a[22];

同时update（原数组的值进行单点修改）与sum（前缀和）也是会经常用到的。

int lowbit(int x)//求子节点的个数
{
	return x & -x;
}
void update(int k,int x)
{
	for(int i = k; i <= n; i += lowbit(i))//单点进行更新，这一个点的父节点也要加上
    //因此i加上lowbit（i）,到达它父节点的下标
		C[i] += x;
}
void Sum(int k)
{
	for(int i = k; i > 0; i -= lowbit(i))//求和函数，由于求1-k的和，c[i]是累加了的
    //因此所有i的子节点都不需要再加。
		B[k] += C[i];	
}

构造树状数组我就不再赘述。这里介绍一下本题需要使用的离散化

离散化的意义

离散化可以有效地降低时间复杂度，对一些无法作为下标进行操作但它们本身属性并不重要的数可以进行操作。

离散化的两种实现方法

(1).数组离散化

操作前后如图

这里其实就是运用一种下标的思想，逆序对知道他们的大小是没有多大用处的，所以我们用离散化，降低数据。noip提高的火柴排队也可以说使用了离散化与归并求逆序对。

for(int i = 1; i <= n; i ++){    
    cin >> a[i].val;    
    a[i].id = i;
}
sort(a + 1, a + n + 1);           //定义结构体时按val从小到大重载
for(int i = 1; i <= n; i ++)    
	  b[a[i].id] = i;                    //将a[i]数组映射成更小的值,b[i]就是a[i]对应的rank(顺序)值

(2).STL+二分离散化

#include<algorithm> // 需要头文件
//n原数组大小   num原数组中的元素    lsh离散化要用的辅助数组    cnt离散化后的数组大小 
int lsh[MAXN] , cnt , num[MAXN] , n;
for(int i=1; i<=n; i++) 
{	
      scanf("%d",&num[i]);	
      lsh[i] = num[i];	//复制一份原数组
}
sort(lsh+1 , lsh+n+1); //排序，unique虽有排序功能，但交叉数据排序不支持，所以先排序防止交叉数据
//cnt就是排序去重之后的长度
cnt = unique(lsh+1 , lsh+n+1) - lsh - 1; //unique返回去重之后最后一位后一位地址 - 数组首地址 - 1
for(int i=1; i<=n; i++)	
      num[i] = lower_bound(lsh+1 , lsh+cnt+1 , num[i]) - lsh;
//lower_bound返回二分查找在去重排序数组中第一个等于或大于num[i]的值的地址 - 数组首地址 ，从而实现离散化

解释一下unique吧。平常没有怎么用（对于我来说）

unique函数属于STL中的函数，它的功能是元素去重。即”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素给占领了(详细情况，下面会讲)。由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。因此如果相同的数相隔较远，那么便不能够完全去重，所以先用sort排序。这里要注意一下，并这道题并不能说原数组有重复就要删去，因此我们离散化还是要覆盖原数组的每一个数

弄完离散之后，我们便可以考虑构造树状数组了。构造树状数组有点难以描述，通过构造，我们可以得到sum(k)就是得到了顺序对的个数，那么用这一个i也就是表示原数是第几个数来减去这一个顺序对个数即可。来个图例

根据图片，树状数组C其实就是B数组从1-6进行遍历进行更值的。到i时，c[b[i]]就要加1，同时，它的父节点也要弄。就相当于update(k,1)。

具体操作见代码

/*
    树状数组模板题。
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
struct node {
    int num,val;
    bool operator < (const node &x)const {
        if (x.val < val)
            return 0;
        else
            return 1;
    }
};
int n,b[100005],c[100005],a[100005];
long long ans;
int lowbit (int x){//lowbit(x)表示第x个数的子节点个数。
    return x & -x;
}
void update(int k){//单个点值进行改变。
    for (int i = k ;i <= n ;i += lowbit(i))
        c[i] += 1;
}
long long  sum (int k){//求前缀和
    long long tot = 0;
    for (int i = k;i >=1 ;i -=lowbit(i))
        tot += c[i];
    return tot;
}
int main(){
    scanf ("%d",&n);
    for (int i = 1;i <= n; i ++ ){
        scanf ("%d",&a[i]);
        b[i] = a[i];
    }
    //以下全是进行离散化处理，从小到大，求出逆序对个数，同时还要进行去重。
    //两种处理方法，一是数组，一是STL
    sort(b + 1,b + 1 + n);
    int cnt = unique(b + 1,b + 1 + n) - b - 1;
    for (int i = 1;i <= n;i ++)
        a[i] = lower_bound(b + 1,b + 1 + cnt,a[i]) - b;
    /*int cnt = 0;//数组进行离散化
    for (int i = 1;i <= n; i ++){
        if (a[i].val != a[i - 1].val)
            cnt ++;
        b[a[i].num] = cnt;
    }*/
    for (int i = 1;i <= n;i ++ ){
        update(a[i]);//相当于构造树状数组
        ans += i - sum(a[i]); //求出前缀和，sum其实就表示第i个数前面小于这一个数的。用i减去这一个前缀和，就求出了在i前面比第i个数小的数。
    }
    printf("%lld",ans);
}