算法笔记:逆序对问题
逆序对问题介绍
逆序对的定义
逆序对:对于一段给定的正整数序列,逆序对就是序列中满足 并且 的有序对
可以简单理解为数列本来是单调不减的,但是出现了前面的数比后面的数大的情况,这就构成了一个逆序
逆序对问题就是求序列中逆序对的数量
逆序对问题的暴力求法
这个问题显然可以通过双指针求解
即一个指针 遍历整个序列,另一个指针 遍历 前面所有的数,如果 则逆序对数增加
时间复杂度为
代码如下
ll getInversion(const vector<int>& a) {
ll res = 0;
for (int i = 0; i < (int)a.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (a[j] > a[i]) {
++res;
}
}
}
return res;
}想要具体感受逆序对问题,可以参考这题 Luogu P1908 逆序对
解决逆序对问题的方法
分治
考虑分治,将整个序列分为两个部分求解,那么最后的结果就是,左半部分逆序对的数量+右半部分逆序对的数量+两部分合并后逆序对的数量
base case 显然是序列中只有一个元素,此时其对整体逆序对数量的贡献是 0
所以接下来只需要考虑合并两部分过程中产生的逆序对的数量
注意到如果两部分有序,可以简化时间复杂度,因此在分治的过程中,我们可以顺手给序列进行排序,因此自然想到归并排序(因此使用分治法解决逆序对问题实际上是在归并排序的基础上进行扩展)
如果两部分有序,可以采用双指针
如图,当 时,说明 小于右半部分 之后所有的数,因此移动左指针
当 时,说明 小于左半部分 及其后面所有的数,此时逆序对数量增加(可以直接计算求得),然后移动右指针
如此可以在线性时间内求出一层合并过程产生的逆序对的对数
而长度为 的序列递归搜索树一共有 层,因此时间复杂度为
实现代码如下
const int N = 1e5 + 10;
int tmp[N];
ll getInversion(vector<int>& a, int l, int r) {
if (l >= r) {
return 0;
}
int m = (l + r) >> 1;
ll left = getInversion(a, l, m);
ll right = getInversion(a, m + 1, r);
// 计算合并过程产生的逆序对数
int i = l, j = m + 1;
ll merge = 0;
while (i <= m && j <= r) {
if (a[i] <= a[j]) {
++i;
} else {
merge += m - i + 1;
++j;
}
}
// merge
i = l, j = m + 1;
int k = l;
while (i <= m && j <= r) {
tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
}
while (i <= m) {
tmp[k++] = a[i++];
}
while (j <= r) {
tmp[k++] = a[j++];
}
for (int p = l; p <= r; ++p) {
a[p] = tmp[p];
}
return left + right + merge;
}注意到合并和统计的过程实际上可以合在一起,因此可以得到下面的代码
const int N = 1e5 + 10;
int tmp[N];
ll getInversion(vector<int>& a, int l, int r) {
if (l >= r) {
return 0;
}
int m = (l + r) >> 1;
ll left = getInversion(a, l, m);
ll right = getInversion(a, m + 1, r);
int i = l, j = m + 1, k = l;
ll merge = 0;
while (i <= m && j <= r) {
if (a[i] <= a[j]) {
tmp[k++] = a[i++];
} else {
merge += m - i + 1;
tmp[k++] = a[j++];
}
}
while (i <= m) {
tmp[k++] = a[i++];
}
while (j <= r) {
tmp[k++] = a[j++];
}
for (int p = l; p <= r; ++p) {
a[p] = tmp[p];
}
return left + right + merge;
}树状数组
无离散化
回到暴力解法,我们发现每次固定一个 ,都要去前面遍历一遍来找是否存在 ,使得
如果能够将这个过程“优化”一下,就能够更快地求到逆序对的个数了
换个角度,我们可以用一个桶统计 指针在当前位置时每个数出现的次数,那么我们可以通过前缀和求出 1 ~ i 的所有的数出现的次数,显然这其实就是小于等于 的数的个数
而我们要的是大于 的数的个数,因此用总数 减去这个前缀和即可
然而,前缀和显然无法满足我们的要求,虽然它有优秀的查询效率,但是预处理的时间仍然不可忽略
所以,我们这里使用树状数组进行查询和修改,总时间复杂度为
代码如下
struct BIT {
int n;
vector<ll> tree;
BIT(int n) : n(n), tree(n + 1, 0) {
}
int lowbit(int x) {
return x & -x;
}
void add(int i, ll x) {
while (i <= n) {
tree[i] += x;
i += lowbit(i);
}
}
ll query(int i) {
ll res = 0;
while (i >= 1) {
res += tree[i];
i -= lowbit(i);
}
return res;
}
};
ll getInversion(vector<int>& a) { // a 是 1-index
ll res = 0;
int n = a.size();
int maxn = -1e9;
for (int x : a) {
maxn = max(maxn, x);
}
BIT bt(maxn);
for (int i = 1; i < n; ++i) {
bt.add(a[i], 1);
res += i - bt.query(a[i]);
}
return res;
}离散化
注意到由于需要存每个数的出现次数,因此树状数组的大小取决于序列中数的最大值
并且,当序列中如果存在非正数,还会因为访问错误的下标而报错
因此使用树状数组求逆序对问题,常常需要离散化
ll getInversion(vector<int>& a) { // 0-index
int n = a.size();
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
BIT bt(b.size());
ll res = 0;
for (int i = 0; i < n; ++i) {
int rank = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
bt.add(rank, 1);
res += i + 1 - bt.query(rank);
}
return res;
}逆序对问题拓展
相邻元素交换次数等于逆序对数
可以参考 Luogu P1774 最接近神的人
这题给定一个序列,允许我们对相邻元素进行交换,最终使得序列单调不减,求最小的交换次数
这和逆序对有什么关系?
实际上,我们始终把大的元素交换到后面,而每交换一次,就会恰好减少一个逆序对
因此,这题实际上就是在给定一个序列,求这个序列逆序对的数量
非单调不减逆序对
此题给定两个序列,要求将一个序列通过相邻元素交换后得到另一个序列的最少交换次数
实际上,如果将目标序列映射成一个新的单调不减的序列,然后将原序列中的值改为新的映射值。显然不能够一个字母对应一个新的映射值,因为字母不唯一
这时可以考虑按顺序以此映射相同的字母,如此这个问题就又变为了普通的逆序对问题
代码如下
void solve() {
int n;
cin >> n;
string a, b;
cin >> a >> b;
for (int i = 0; i < n; ++i) {
int l = b[i] - 'A';
pos[l].push(i + 1); // 1-index
}
vector<int> arr(n + 1);
int mx = 0;
for (int i = 0; i < n; ++i) {
int l = a[i] - 'A';
int rk = pos[l].front();
pos[l].pop();
mx = max(mx, rk);
arr[i + 1] = rk;
}
BIT bt(mx + 1);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
bt.add(arr[i], 1);
ans += i - bt.query(arr[i]);
}
cout << ans << endl;
}三元上升子序列
可以参考 Luogu P1637 三元上升子序列
这题给定一个序列,要找满足 且 的子序列的个数
有了逆序对的经验,单独求 的对数和 的对数都是非常简单的
现在要求 的对数,显然只需要把两部分分别求出来再相乘即可
代码如下:
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
int mx = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
mx = max(mx, a[i]);
}
BIT bt1(mx), bt2(mx);
vector<int> pre(n + 1), suf(n + 1);
for (int i = 1; i <= n; ++i) {
bt1.add(a[i], 1);
pre[i] = bt1.query(a[i] - 1);
}
for (int i = n; i >= 1; --i) {
bt2.add(a[i], 1);
suf[i] = n - i + 1 - bt2.query(a[i]);
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans += 1ll * pre[i] * suf[i];
}
cout << ans << endl;
}如果数据较大或者出现负数,也可以采取下面离散化的写法
void solve() {
int n;
cin >> n;
vector<int> a(n, 0);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
auto rank = [&](int x) -> int { return lower_bound(b.begin(), b.end(), x) - b.begin() + 1; };
BIT bt1(b.size()), bt2(b.size());
vector<int> pre(n), suf(n);
for (int i = 0; i < n; ++i) {
int rk = rank(a[i]);
bt1.add(rk, 1);
pre[i] = bt1.query(rk - 1);
}
for (int i = n - 1; i >= 0; --i) {
int rk = rank(a[i]);
bt2.add(rk, 1);
suf[i] = n - i - bt2.query(rk);
}
ll ans = 0;
for (int j = 0; j < n; ++j) {
int rk = rank(a[j]);
ans += 1ll * pre[j] * suf[j];
}
cout << ans << endl;
}