1 逆序对
给定数组
的下标对
例如
2 固定右端点
从左到右扫描,处理位置
按右端点分类,每个逆序对恰好被统计一次。
困难在于:不能为了每个
3 按值统计
基础篇的树状数组按原数组位置存元素和。本篇改用值域上的频次桶:
树状数组维护 sum(v) 表示已经扫描的元素中,值小于等于
在处理
对
| 当前值 | 前面已有 | 前面小于等于当前值 | 前面大于当前值 | 累计答案 |
|---|---|---|---|---|
| 3 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
| 4 | 2 | 2 | 0 | 1 |
| 5 | 3 | 3 | 0 | 1 |
| 2 | 4 | 1 | 3 | 4 |
每次查询后再执行 add(a[j],1),将当前元素加入频次桶,供后续位置使用。
4 离散化
值可能很大、为零或为负数,不能直接拿原值作为树状数组下标。
逆序对只关心大小关系,因此可以进行 离散化:复制原数组,排序去重,将每个值映射到其排名
例如:
相等值映射到同一排名,严格大小关系保持不变,所以逆序对数量不变。只排序副本,扫描时仍按原数组顺序,否则会丢失
离散化后,公式为:
int rank = int(lower_bound(b + 1, b + m + 1, a[j]) - b);
answer += (j - 1LL) - sum(rank);
add(rank, 1);
此处树状数组长度是不同值的数量
4.1 重复值
对数组 sum(rank) 包含,不会被误计为更大的数。最后的
若从右向左扫描,则应查询 sum(rank-1),统计右侧严格小于当前值的数量。两种方向都可行,但不等号和查询边界必须对应。
5 正确性
处理第
sum(rank) 统计这些元素中小于等于
6 代码实现
格式与 luogu P1908: 逆序对 一致:输入
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 5;
int n, m;
long long a[maxn], b[maxn];
int c[maxn]; // 离散值域上的频次和
int lowbit(int x) { return x & -x; }
void add(int p, int v) {
for (int i = p; i <= m; i += lowbit(i)) c[i] += v;
}
int sum(int x) {
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) res += c[i];
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
b[i] = a[i];
}
sort(b + 1, b + n + 1);
m = int(unique(b + 1, b + n + 1) - b - 1);
long long answer = 0;
for (int j = 1; j <= n; ++j) {
int rank = int(lower_bound(b + 1, b + m + 1, a[j]) - b);
answer += (j - 1LL) - sum(rank);
add(rank, 1);
}
cout << answer << '\n';
return 0;
}
排序、二分排名和树状数组操作的总时间为 maxn 预留容量。
频次和不超过 int;答案最多为 long long。例如
6.1 示例
输入:
5
3 1 4 5 2
输出:
4
7 练习
完成 luogu P1908: 逆序对,再分别检查:
:答案为 。 :答案为 。 :答案为 。 :答案为 。
还可以把目标改成“前面严格小于当前值的数量”,写出应查询的前缀范围。
参考结果
处理当前值之前查询 sum(rank-1)。查询 sum(rank) 会额外计入相等值。
8 相关题解
暂无相关题解