P1908 逆序对

Posted Fri Mar 13 2020. 1954 words. 10 min read.

This article was last updated on days ago, the information described in the article may be outdated.

题目

[1]

猫猫 TOM 和小老鼠 JERRY 最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。

最近,TOM 老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中满足 ai>aja_i>a_ji<ji<j 的有序对。知道这概念后,他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。

Update:数据已加强。

输入格式

第一行,一个数 nn,表示序列中有 nn 个数。

第二行 nn 个数,表示给定的序列。序列中每个数字不超过 10910^9

输出格式

输出序列中逆序对的数目。

输入输出样例

输入 #1

6
5 4 2 6 3 1

输出 #1

11

说明/提示

对于 25%25\% 的数据,n2500n \le 2500
对于 50%50\% 的数据,n4×104n \le 4 \times 10^4
对于所有数据,n5×105n \leq 5 \times 10^5
请使用较快的输入输出
应该不会 O(n2)O(n^2) 过 50 万吧 by chen_zhechen\_zhe

题解[2]

归并排序

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并排序是一种稳定的排序方法。

归并排序
时间复杂度 O(n  log  n)O(n\;log\;n)
空间复杂度 O(n)O(n)

算法图解

就是先进行拆分,拆到只剩下自己的时候再进行合并

以样例作为例子

拆分

先定义一个 msort 函数将原序列拆分

int msort(int L, int R) {
int mid = (L + R) / 2;
if(L == R) return;
msort(L, mid);
msort(mid+1, R);
}

合并

因为可以保证需要合并的两组数都是单调的,所以我们只需要从两组数的最左边开始比较,若 ai>aja_i>a_j 我们就可以将 aja_j 存入 temp 数组中,然后 j++,在将 aia_iaja_j 进行比较,一直重复进行,知道 i 或者 j 超出了范围

int i = L, j = mid + 1, t = L;
while(i<=mid && j<=R) {
if (a[i] > a[j]) {
ans += mid - i + 1;
temp[t++] = a[j];
j++;
}
else {
temp[t++] = a[i];
i++;
}
}

完成后我们会得到一个同样单调的 temp 数组,但是 temp 中只存了中较小的值,所以我们还需要将 a 中剩下的值存进来,这也是为什么我们需要在外部定义 i 和 j,可以记录下还有哪些没被存进去

while (i <= mid) {
temp[t++] = a[i];
i++;
}
while (j <= R) {
temp[t++] = a[j];
j++;
}

最后我们再将temp数组拷贝回a数组

for (int k=L; k<=R; k++)
a[k] = temp[k];

步骤分解

肯能看到这还是很懵
那就看看详细的步骤分解吧

合并 5 4,i=L=1i=L=1mid=L+R2=1mid=\frac{L+R}{2}=1j=mid+1=2j=mid+1=2ai>aja_i>a_j,将 aja_j 存入 temp,temp 数组:4 5 0 0 0 ,j++,j=3,超出范围,将剩余的 5 存入,temp 数组:4 5 2 6 3 1

合并 3 6,i=L=4i=L=4,,mid=L+R2=4mid=\frac{L+R}{2}=4j=mid+1=5j=mid+1=5ai>aja_i>a_j,将aja_j存入 temp,temp 数组:4 5 0 3 6 0,j++,j=6,超出范围,将剩余 3 存入,temp 数组:4 5 2 3 6 1

合并 3,5 和 2,i=L=1i=L=1mid=L+R2=2mid=\frac{L+R}{2}=2j=mid+1=3j=mid+1=3ai>aja_i>a_j,将 aja_j 存入 temp,temp 数组:2 5 0 3 6 0,j++,j=4,超出范围,将剩余 4 5 存入,temp 数组:2 4 5 3 6 0

合并 1 和 3,6,i=L=4i=L=4mid=L+R2=4mid=\frac{L+R}{2}=4j=mid+1=6j=mid+1=6ai>aja_i>a_j,将 aja_j 存入 temp,temp 数组:2 5 0 1 6 0,j++,j=7,超出范围,将剩余 3 6 存入,temp 数组:2 4 5 1 3 6

合并 2 4 5 和 1 3 6

i=L=1, mid=L+R2=3, j=mid+1=4 ai>aj, ajtemp, temp150160 j++, j=5, ai<aj, aitemp, temp120160 i++, i=2, ai>aj, ajtemp, temp123160 j++, j=6, ai<aj, aitemp, temp123460 i++, i=3, ai<aj, aitemp, temp123450 i++, i=3, mid, 6, temp123456i=L=1,\ mid=\frac{L+R}{2}=3,\ j=mid+1=4 \\ ~\\ a_i>a_j,\ 将a_j存入temp,\ temp数组:1\,5\,0\,1\,6\,0 \\ ~\\ j++,\ j=5,\ a_i<a_j,\ 将a_i存入temp,\ temp数组:1\,2\,0\,1\,6\,0 \\ ~\\ i++,\ i=2,\ a_i>a_j,\ 将a_j存入temp,\ temp数组:1\,2\,3\,1\,6\,0 \\ ~\\ j++,\ j=6,\ a_i<a_j,\ 将a_i存入temp,\ temp数组:1\,2\,3\,4\,6\,0 \\ ~\\ i++,\ i=3,\ a_i<a_j,\ 将a_i存入temp,\ temp数组:1\,2\,3\,4\,5\,0 \\ ~\\ i++,\ i=3,\ 超出mid,\ 将剩余 6 存入,\ temp数组:1\,2\,3\,4\,5\,6\\

这样就能得到一个有序数列了,例子中讲的是升序,降序也是同样的道理

逆序对

然鹅这题是求逆序对,所以我们还需要在此基础上加上一行

在判断ai<aja_i<a_j的时候,前面的数小于后面的数,这时逆序对就出现了!

由于 L ~ mid 和 mid + 1 ~ r 都是有序序列
所以一旦 l ~ mid 中的元素 > mid + 1 ~ r 中的元素
又因为第 i 个元素 < i + 1 ~ mid 那么i + 1 ~ mid 的元素都 > 第 j 个元素
所以 ans 加的元素个数就是 i ~ mid 的元素个数,也就是 mid - i + 1

#include <cstdio>
#define MAXN 5000010

long long ans; //据说需要 long long,都 5x10^5 了,逆序对有又那么多,肯定要啦
int n, a[MAXN], temp[MAXN];

//快读
int read() {
bool flag = 0; int x = 0; char ch = getchar();
while(ch<'0' || ch>'9') {if(ch == '-') flag = 1; ch = getchar();}
while(ch>='0' && ch <= '9') {x *= 10; x += ch - '0'; ch = getchar();}
return flag ? - x : x;
}

//归并排序
void msort(int L, int R) {
int mid = (L + R) / 2;
if(L == R) return;
msort(L, mid);
msort(mid+1, R);
int i = L, j = mid + 1, t = L;
while(i<=mid && j<=R) {
if (a[i] > a[j]) {
ans += mid - i + 1; //逆序对计数
temp[t++] = a[j];
j++;
}
else {
temp[t++] = a[i];
i++;
}
}
while (i <= mid) {
temp[t++] = a[i];
i++;
}
while (j <= R) {
temp[t++] = a[j];
j++;
}
for (int k=L; k<=R; k++) a[k] = temp[k];
return;
}

int main() {
n = read(); //都提示用较快的输入输出了你还在cin?
for (int i=1; i<=n; i++) a[i] = read();
msort(1, n);
printf("%lld", ans); //%lld别错了
return 0; //好习惯
}


Comments

Unable to load Disqus, please make sure your network can access.