逆序对

定义：一对下标(i,j)如果满足i<j且a[i]>a[j]那么他们是逆序对

逆序对的个数，也是冒泡排序的交换次数

如果数组中互不相同，交换数组中任意两个元素，一定改变逆序对个数的奇偶性

求逆序对主要有两个方法：归并排序 和 树状数组

高维逆序对/顺序对

二维偏序：排序 树状数组 / 排序 线段树 / 排序 cdq分治(类似归并排序)
三维偏序：排序 cdq分治 树状数组
四维偏序：排序 cdq分治套cdq分治 树状数组

参考题目

P1116 车厢重组

https://www.luogu.com.cn/problem/P1116

题目描述

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转$180$度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

输入格式

共两行。

第一行是车厢总数$N( \le 10000)$。

第二行是$N$个不同的数表示初始的车厢顺序。

输出格式

一个整数，最少的旋转次数。

样例 #1

样例输入 #1

4
4 3 2 1 

样例输出 #1

6

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, a[10000], z;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (a[j] > a[i]) {
				z++;
			}
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

P1908 逆序对

https://www.luogu.com.cn/problem/P1908

题目描述

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

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

Update:数据已加强。

输入格式

第一行，一个数 $n$，表示序列中有 $n$个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

输出格式

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

样例 #1

样例输入 #1

6
5 4 2 6 3 1

样例输出 #1

11

提示

对于 $25\%$ 的数据，$n \leq 2500$

对于 $50\%$ 的数据，$n \leq 4 \times 10^4$。

对于所有数据，$n \leq 5 \times 10^5$

请使用较快的输入输出

应该不会 $O(n^2)$ 过 50 万吧 by chen_zhe

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[500020];
int b[500020];
int c[500020];
void change(int x, int y) {
	for (int i = x; i <= n; i += i & -i) {
		c[i] += y;
	}
}
int query(int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re += c[i];
	}
	return re;
}
int main() {
	scanf("%d", &n);
	m = n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		b[i] = a[i];
	}
	sort(b, b + m);
	m = unique(b, b + m) - b;
	for (int i = 0; i < n; i++) {
		a[i] = lower_bound(b, b + m, a[i]) - b + 1;
	}
	long long ans = 0;
	for (int i = n - 1; i >= 0; i--) {
		ans += query(a[i] - 1);
		change(a[i], 1);
	}
	cout << ans << endl;
	return 0;
}

题解

2个做法

1. 归并排序 merge sort / CDQ divide and conquer
2. 排序/离散化 树状数组 sort and bit

50 -> 5
40 -> 4
20 -> 2
60 -> 6
30 -> 3
10 -> 1

sort unique lower_bound
离散化代码

for (int i = 0; i < n; i++)
{
    cin >> a[i];
    b[i] = a[i];
}
int m = n;
sort(b, b + m);
m = unique(b, b + m) - b;
for (int i = 0; i < n; i++)
{
    a[i] = lower_bound(b, b + m, a[i]) - b;
}

离散化之后可以认为每个数字的范围是1到n

50 40 20 60 30 10
1 2 3 4 5 6

10 20 30 40 50 60
6 3 5 2 1 4

i < j && a[i] > a[j]

初始
6
5 4 2 6 3 1

0 0 0 0 0 0

倒数第1个数字是1
有0个小于1的数字，ans += 0
第1个位置+=1
1 0 0 0 0 0

倒数第2个数字是3
有1个小于3的数字，ans += 1
第3个位置+=1
1 0 1 0 0 0

倒数第3个数字是6
有2个小于6的数字，ans += 2
第6个位置+=1
1 0 1 0 0 1

倒数第4个数字是2
有1个小于2的数字，ans += 1
第2个位置+=1
1 1 1 0 0 1

倒数第5个数字是4
有3个小于4的数字，ans += 3
第4个位置+=1
1 1 1 1 0 1

倒数第6个数字是5
有4个小于5的数字，ans += 4
第5个位置+=1
1 1 1 1 1 1

1. 归并排序
   推广，可以得到CDQ分治

2. 离散化，树状数组

500 400 200 600 300 100
离散化
5 4 2 6 3 1

另外一种做法：
按照 (值，位置) 排序
sort then (value, position)
树状数组维护n个位置
create a BIT with length n
从大到小扫描所有(值，位置)
scan all pairs

c是一个数组，可以被树状数组优化

for (int i = n; i > 0; i--)
{
    ans += c[1] + c[2] + ... + c[a[i]-1]
    c[a[i]] += 1
}

for (int i = n-1; i >= 0; i++) // 从大到小枚举
// from last to first
{
ans += query(a[i].position)
// 1..a[i].position 所有位置之和
// find the sum of 1..a[i].position
// 小于等于自己的位置有几个比自己大？
// how many j, j > i && a[j].position < a[i].position
// 比自己大，就是在自己之前加入
change(位置, 1);
change(a[i].position, 1);
}

有时，不只需要知道全部有多少个逆序对
需要对于每个数字求出
自己之前有多少个比自己大的
自己之后有多少个比自己小的

https://www.luogu.com.cn/blog/ryoku/solution-p1908
相同的情况会不会出错？

Count the number of inversions in a permutation
1 <= a[i] <= n

for (int i = 1; i <= n; i++)
{
// query(n) == i-1
ans += i - 1 - query(a[i]); // a[i+1] + a[i+2] + ... + a[n]
change(a[i], 1);
}

P1774 最接近神的人

https://www.luogu.com.cn/problem/P1774

题目描述

破解了符文之语，小FF开启了通往地下的道路。当他走到最底层时，发现正前方有一扇巨石门，门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“神的殿堂”。小FF猜想里面应该就有王室的遗产了。但现在的问题是如何打开这扇门……

仔细研究后，他发现门上的图案大概是说：古代人认为只有智者才是最容易接近神明的。而最聪明的人往往通过一种仪式选拔出来。仪式大概是指，即将隐退的智者为他的候选人写下一串无序的数字，并让他们进行一种操作，即交换序列中相邻的两个元素。而用最少的交换次数使原序列变成不下降序列的人即是下一任智者。

小FF发现门上同样有着n个数字。于是他认为打开这扇门的秘诀就是找到让这个序列变成不下降序列所需要的最小次数。但小FF不会……只好又找到了你，并答应事成之后与你三七分……

输入格式

第一行为一个整数n，表示序列长度

第二行为n个整数，表示序列中每个元素。

输出格式

一个整数ans，即最少操作次数。

样例 #1

样例输入 #1

4
2 8 0 3

样例输出 #1

3

提示

对于30%的数据1≤n≤10^4。

对于100%的数据1≤n≤5*10^5；

-maxlongint≤A[i]≤maxlongint。

样例说明：开始序列为2 8 0 3，目标序列为0 2 3 8，可进行三次操作的目标序列：

1．Swap (8,0):2  0  8  3

2．Swap (2,0):0  2  8  3

3．Swap (8,3):0  2  3  8

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
pair<int, int> a[500020];
int c[500020];
void change(int x, int y) {
	for (int i = x; i <= n; i += i & -i) {
		c[i] += y;
	}
}
int query(int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re += c[i];
	}
	return re;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i].first);
		a[i].second = i + 1;
	}
	sort(a, a + n);
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		ans += i - query(a[i].second);
		change(a[i].second, 1);
	}
	cout << ans << endl;
	return 0;
}

题解

4
2 8 0 3
离散化之后变成
2 4 1 3

另一个方法把位置按照值排序
(2, 1)
(8, 2)
(0, 3)
(3, 4)

(0, 3)
(2, 1)
(3, 4)
(8, 2)

3 1 4 2 的逆序对个数和 2 8 0 3 的逆序对个数一样

复杂的逆序对

注意同一列火柴的高度互不相同
输入
4
1 3 4 2
1 7 2 4

两行分别离散化
1 3 4 2
1 4 2 3

通过相同的数字换相同的数字，把第一行换成1到n
（也可以理解为把b[i] 换成 a[j] == b[i] 的 j）
1 2 3 4
1 3 4 2

对第二行的排列求逆序对的个数

P1966 [NOIP2013 提高组] 火柴排队

https://www.luogu.com.cn/problem/P1966

题目描述

涵涵有两盒火柴，每盒装有 $n$ 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：$\sum (a_i-b_i)^2$

其中 $a_i$ 表示第一列火柴中第 $i$ 个火柴的高度，$b_i$ 表示第二列火柴中第 $i$ 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 $10^8-3$ 取模的结果。

输入格式

共三行，第一行包含一个整数 $n$，表示每盒中火柴的数目。

第二行有 $n$ 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 $n$ 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

输出格式

一个整数，表示最少交换次数对 $10^8-3$ 取模的结果。

样例 #1

样例输入 #1

4
2 3 1 4
3 2 1 4

样例输出 #1

1

样例 #2

样例输入 #2

4
1 3 4 2
1 7 2 4

样例输出 #2

2

提示

【输入输出样例说明一】

最小距离是$0$，最少需要交换 $1$ 次，比如：交换第 $1$列的前$2$ 根火柴或者交换第 $2$ 列的前 $2$根火柴。

【输入输出样例说明二】

最小距离是 $10$，最少需要交换 $2$ 次，比如：交换第 $1$ 列的中间 $2$ 根火柴的位置，再交换第 $2$ 列中后 $2$ 根火柴的位置。

【数据范围】

对于 $10\%$ 的数据， $1 \leq n \leq 10$；

对于 $30\%$ 的数据，$1 \leq n \leq 100$；

对于 $60\%$ 的数据，$1 \leq n \leq 10^3$；

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$，$0 \leq$ 火柴高度 $< 2^{31}$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
pair<int, int> a[100020];
pair<int, int> b[100020];
int r[100020];
int c[100020];
void change(int x, int y) {
	for (int i = x; i <= n; i += i & -i) {
		c[i] += y;
	}
}
int query(int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re += c[i];
	}
	return re;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i].first);
		a[i].second = i;
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &b[i].first);
		b[i].second = i;
	}
	sort(a, a + n);
	sort(b, b + n);
	for (int i = 0; i < n; i++) {
		r[a[i].second] = b[i].second + 1;
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		ans += i - query(r[i]);
		change(r[i], 1);
	}
	cout << ans % 99999997 << endl;
	return 0;
}

题解

P1637 三元上升子序列

https://www.luogu.com.cn/problem/P1637

题目描述

Erwin 最近对一种叫 thair 的东西巨感兴趣。。。

在含有 $n$ 个整数的序列 $a_1,a_2,\ldots,a_n$ 中，三个数被称作thair当且仅当 $i<j<k$ 且 $a_i<a_j<a_k$。

求一个序列中 thair 的个数。

输入格式

开始一行一个正整数 $n$,

以后一行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

一行一个整数表示 thair 的个数。

样例 #1

样例输入 #1

4
2 1 3 4

样例输出 #1

2

样例 #2

样例输入 #2

5
1 2 2 3 4

样例输出 #2

7

提示

样例2 解释

$7$ 个 thair 分别是：

• 1 2 3
• 1 2 4
• 1 2 3
• 1 2 4
• 1 3 4
• 2 3 4
• 2 3 4

数据规模与约定

• 对于 $30\%$ 的数据 保证 $n\le100$；
• 对于 $60\%$ 的数据 保证 $n\le2000$；
• 对于 $100\%$ 的数据 保证 $1 \leq n\le3\times10^4$，$0\le a_i\leq 10^5$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[500020];
int b[500020];
int c[500020];
int d[500020];
void change(int *c, int x, int y) {
	for (int i = x; i <= n; i += i & -i) {
		c[i] += y;
	}
}
int query(int *c, int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re += c[i];
	}
	return re;
}
int main() {
	scanf("%d", &n);
	m = n;
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		b[i] = a[i];
	}
	sort(b, b + m);
	m = unique(b, b + m) - b;
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		a[i] = lower_bound(b, b + m, a[i]) - b + 1;
		ans += query(d, a[i] - 1);
		change(d, a[i], query(c, a[i] - 1));
		change(c, a[i], 1);
	}
	cout << ans << endl;
	return 0;
}

题解

第一种做法：
枚举j，问左边有多少个比自己小的，问右边有多少个比自己大的

第二种做法：

两个树状数组
第一个记录以每个数字结尾长度为1的序列有多少个
第二个记录以每个数字结尾长度为2的序列有多少个

逆序对

1. 归并排序（类似于分治）
2. 排序，树状数组

现在问的逆序对，都是全局的逆序对
假设问的是
对于每个i，
有多少个j满足j < i && a[j] > a[i]
有多少个j满足i < j && a[i] > a[j]

(二维)顺序对
i < j && a[i] < a[j]

(三维)顺序对
i < j && a[i] < a[j] && b[i] < b[j]
分治（CDQ分治）

abc244_d Swap Hats

https://atcoder.jp/contests/abc244/tasks/abc244_d
输入两个RGB的排列
一次操作就是交换两个字符
问能不能操作恰好10**18次
把第一个排列变成第二个排列

参考代码

#include <bits/stdc++.h>
using namespace std;
char a, b, c;
int z;
int main()
{
	cin >> a >> b >> c;
	z += (a > b) + (b > c) + (a > c);
	cin >> a >> b >> c;
	z += (a > b) + (b > c) + (a > c);
	cout << (z & 1 ? "No" : "Yes") << endl;
	return 0;
}

题解

输入两个RGB的排列
一次操作就是交换两个字符
问能不能操作恰好10**18次
把第一个排列变成第二个排列

CF1676H2 Maximum Crossings (Hard Version)

https://codeforces.com/problemset/problem/1676/H2
https://www.luogu.com.cn/problem/CF1676H2

参考代码

题解

相等也算逆序对

spoj MEANARR

https://www.spoj.com/problems/MEANARR/
多少个部分和 >= 0

spoj PARAG

https://www.spoj.com/problems/PARAG/

spoj INVCNT

https://www.spoj.com/problems/INVCNT/

https://atcoder.jp/contests/abc261/tasks/abc261_f