统计"进入顺序"中的顺序对(非逆序对)数量。
N 名同学学号 0 ~ N−1,按给定顺序依次进入教室。每位同学进入时,要和已经在教室内、且学号小于自己的同学握手。求全班一共握手多少次。
顺序对计数归并排序逆序对变体树状数组
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N;第二行是进入顺序(学号排列) |
| 输出 | 握手总次数 |
| 数据范围 | 2 ≤ N ≤ 3 × 10⁵ |
| 序列性质 | 是 0 ~ N−1 的一个排列 |
| 答案可能很大 | 最大可达 N(N−1)/2 ≈ 4.5 × 10¹⁰ |
a_i < a_j(i < j)C(N,2) − 逆序对数逐个同学模拟一遍,同时用"顺序对"视角核对。
| 次序 | 进入者学号 | 教室内已有 | 其中比它学号小的 | 本次握手 |
|---|---|---|---|---|
| 1 | 2 | (空) | — | 0 |
| 2 | 1 | 2 | 无(1 < 2 不满足) | 0 |
| 3 | 3 | 1, 2 | 1、2 都小于 3 | 2 |
| 4 | 0 | 1, 2, 3 | 无(0 最小) | 0 |
总计 2 ✓
序列 a = [2, 1, 3, 0]
所有 i < j 的配对,检查 a_i < a_j:
(2,1) → 2 > 1 ✗
(2,3) → 2 < 3 ✓
(2,0) → 2 > 0 ✗
(1,3) → 1 < 3 ✓
(1,0) → 1 > 0 ✗
(3,0) → 3 > 0 ✗
共 2 个 ✓
✅ 与模拟一致
4 + 2 = C(4,2) = 6 ✓。两者互补,所以也可以"统计逆序对再取补"。学号递增入场,每个新来的学号都是教室里最大的,所以要跟所有人握手。
第 1 位(0):0 人
第 2 位(1):1 人
第 3 位(2):2 人
第 4 位(3):3 人
第 5 位(4):4 人
第 6 位(5):5 人
合计 0 + 1 + 2 + 3 + 4 + 5 = 15
✅ 15
这种情况所有配对都握手
总数 = C(6,2) = 6 × 5 / 2 = 15 ✓
✅ 一致
| 序列特点 | 顺序对数量 | 说明 |
|---|---|---|
| 严格递增 | C(N,2)(最大) | 人人都和所有人握手 |
| 严格递减 | 0(最小) | 每次来的都是最小的,无人可握 |
| 随机排列 | 介于两者之间 | 期望约 C(N,2)/2 |
分治合并时累计"顺序对"贡献
从左到右扫描,用 BIT 查询"已出现且比当前小的个数"
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 归并排序 | O(N log N) | 约 30 行 |
| 树状数组 | O(N log N) | 约 25 行 |
| 双重循环 | O(N²) = 4.5 × 10¹⁰ | ❌ 超时 |
输入进入顺序,程序用暴力法统计顺序对(演示规模内),并展示每位同学的握手次数。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int a[300005], tmp[300005]; long long ans = 0; void mergeSort(int l, int r) { if (l >= r) return; int mid = (l + r) / 2; mergeSort(l, mid); mergeSort(mid + 1, r); int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { if (a[i] < a[j]) { // 取左半元素:它比右半"剩余"的都小,产生顺序对 ans += (long long)(r - j + 1); tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; } } while (i <= mid) tmp[k++] = a[i++]; while (j <= r) tmp[k++] = a[j++]; for (int t = l; t <= r; t++) a[t] = tmp[t]; } int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", &a[i]); mergeSort(0, N - 1); printf("%lld\n", ans); return 0; }
r − j + 1?因为此时右半还没被取走的元素是 a[j..r],它们都比 a[i] 大(因为两半各自有序),所以 a[i] 与这 r − j + 1 个元素都构成"顺序对"(左小右大)✓。mid − i + 1。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
mergeSort(l, mid); mergeSort(mid+1, r); | 分治 | 两半各自有序后才能线性合并 |
if (a[i] < a[j]) ans += r - j + 1; | 核心计数 | 取左半 → 产生顺序对 |
else tmp[k++] = a[j++]; | 取右半 | 不产生顺序对(右元素不更大) |
long long ans | 类型 | 答案可达 4.5 × 10¹⁰,必须 long long |
int 存答案;③ 忘记把临时数组拷回原数组(导致后续层出错);④ 递归深度(N = 3 × 10⁵ 时归并递归深度只有约 19 层,安全)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 2 | 题面样例 1 |
6 | 15 | 题面样例 2 |
2 | 0 | 先来学号 1,后来 0:0 不是更小,不握手 |
2 | 1 | 先来 0,1 进来时学号更大 → 握手 1 次 |
3 | 0 | 严格递减,无人握手 |
3 | 3 | 严格递增,等于 C(3,2) = 3 |
需要与原数组等长的临时数组。
✅ 约 600 万次操作,瞬间完成。相比暴力枚举两两配对的 4.5 × 10¹⁰,快了四个数量级。
// 归并排序统计"顺序对"(左小右大) if (a[i] < a[j]) { ans += r - j + 1; tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; } // 对照:统计"逆序对"(左大右小) if (a[i] <= a[j]) { tmp[k++] = a[i++]; } else { ans += mid - i + 1; tmp[k++] = a[j++]; } // 两者的关系 // 顺序对数 + 逆序对数 = C(N, 2) // 所以统计出任意一个,另一个用总数减即可 // 用树状数组统计"已出现且更小"的个数 // for (i = 0..N-1) { ans += query(a[i] - 1); add(a[i], 1); } // 归并排序还能顺便完成排序,一举两得
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 顺序对 | 左小右大的配对 | 握手、配对、正序关系计数 |
| 逆序对 | 左大右小的配对 | 排序最少交换次数、逆序统计 |
| 互补关系 | 顺序对 + 逆序对 = C(N,2) | 两种统计互相验证 |
C(N,2) − 原答案。同一道题,规则方向一改,答案就是互补的——读题时务必逐字看清。)