关于归并排序求逆序对

之前写了一篇 blog 讲如何用归并排序求逆序对以及解决相关问题。最近才发现自己根本没搞懂，而且写的不好。遂重写。

前言：什么是逆序对？

对于数列的第 i 个和第 j 个元素，若满足 i < j 且 a[i] > a[j]，则其为一个逆序对。

归并排序的过程：将序列分为两部分，先递归将两侧序列排序，后将两个有序序列合并。

合并两个序列时，由于已经是有序序列，所以用双指针，一个从 l 指向 mid，一个从 mid + 1 指向 r。两个指针所指的，不断将更小的那个放到来转运的新序列 b 中。若相等，则优先将前一序列中的元素先放入（保证稳定性）。把剩下的塞进去，最后把新序列里的东西倒腾回去。

这是一个归并排序的码：

void msort(int l, int r)
{
    if(l >= r) return;
    int mid = (l + r) >> 1;
    msort(l, mid);
    msort(mid + 1, r);//递归排序
    int k = 0;
    int i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) b[++ k] = a[i ++];//稳定性
        else b[++ k] = a[j ++];
    }
    while(i <= mid) b[++ k] = a[i ++];//把剩余的部分加进去
    while(j <= r) b[++ k] = a[j ++];
    for(int i = l; i <= r; i ++ ) a[i] = b[i - l + 1];//最后转移到原数组，完成合并
}

逆序对到底怎么求？其实看看这个合并的过程，不难发现过程中就体现出的逆序对。

合并的两段有序序列，a[i] 表示前段，a[j] 表示后段。

合并过程中若 a[j] < a[i] ，则说明构成逆序对。由于两段有序，所以从 a[i] ~ a[mid] 这一段的所有元素都与 a[j] 构成逆序对。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
int n;
ll ans;
int a[N], b[N];
void msort(int l, int r)
{
    if(l >= r) return;
    int mid = (l + r) >> 1;
    msort(l, mid);
    msort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) b[++ k] = a[i ++];
        else
        {
            b[++ k] = a[j ++];
            ans += mid - i + 1;
        }
    }
    while(i <= mid) b[++ k] = a[i ++];
    while(j <= r) b[++ k] = a[j ++];
    for(int i = l; i <= r; i ++ ) a[i] = b[i - l + 1];
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    msort(1, n);
    printf("%lld", ans);
}

1.板子题：洛谷 P5149 会议座位。

好久之前学字典树时就加到题单里了，但由于忘了逆序对怎么求了（？）所以一直没写。今天一看发现是板子。

读完题你就发现这不就是求逆序对吗。

其实用字典树麻烦了。你只需要将每个字符串 map 转换成数字然后套板子。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
ll ans;
int n;
int a2[N], b[N];
string s;
map<string, int> a1;
void msort(int l, int r)
{
    if(l >= r) return;
    int mid = (l + r) >> 1;
    msort(l, mid);
    msort(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
    {
        if(a2[i] <= a2[j]) b[++ k] = a2[i ++];
        else
        {
            b[++ k] = a2[j ++];
            ans += mid - i + 1;
        }
    }
    while(i <= mid) b[++ k] = a2[i ++];
    while(j <= r) b[++ k] = a2[j ++];
    for(int i = l; i <= r; i ++ ) a2[i] = b[i - l + 1];
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ )
    {
        cin >> s;
        a1[s] = i;
    }
    for(int i = 1; i <= n; i ++ )
    {
        cin >> s;
        a2[i] = a1[s];
    }
    msort(1, n);
    printf("%lld", ans);
}

2.P2717 寒假作业

题意：长度为 n 正整数序列，求有多少连续子序列的平均值不小于 k。

暴力的想的话即用前缀和统计，暴力枚举 l 和 r。每一个 \(s[j]-s[i-1]>=k\) 都对答案做出贡献。

然后看这个式子。我们改变一下：\(s[j]-k-(s[i-1]-k)>=0\)。

然后发现如果把前缀和统计在最初的时候就减去 k 的话统计的就是 \(s[j]-s[i-1]>=0\)，移项得到 \(s[j]>=s[i-1]\)。

发现很眼熟，就能发现这就是求顺序对。（总方案数减去逆序对个数）。

一种比较牛逼的策略。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,k;
int a[N];
ll b[N],s[N],ans;
void msort(int l,int r){
	if(l>=r) return;
	int mid=(l+r)>>1;
	msort(l,mid),msort(mid+1,r);
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(s[i]<=s[j]) b[++k]=s[i++];
		else{
			b[++k]=s[j++];
			ans+=mid-i+1;
		}
	}
	while(i<=mid) b[++k]=s[i++];
	while(j<=r) b[++k]=s[j++];
	for(int i=l;i<=r;i++) s[i]=b[i-l+1];
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]-k;
	msort(0,n);
	printf("%lld",(ll)((ll)n*(n+1)/2)-ans); 
}

四倍经验：P7868 [COCI2015-2016#2] VUDU，[ARC075E] Meaningful Mean，P2804 神秘数字。

以后有好题的话会及时补充。