之前写了一篇 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 神秘数字。
以后有好题的话会及时补充。