混合排序算法工作量计算（Out of Sorts）题解

一、问题核心分析

题目要求计算 Bessie 设计的 quickish_sort 算法的总工作量（work_counter 的最终值）。该算法的核心逻辑是：

1. 对当前数组反复执行 bubble_sort_pass（每次执行工作量累加数组长度），直到数组出现至少一个分隔点；
2. 按分隔点分割数组，对每个子数组递归执行上述过程。

分隔点的定义是：数组前 i 个元素的最大值 ≤ 第 i+1 个元素之后的最小值。关键观察是：

• 排序后的数组中，每个位置 i（1≤i≤n-1）都是分隔点（前 i 个元素是排序后的前 i 小值，后 n-i 个是后 n-i 大值）；
• 原算法的分隔点本质是“排序后数组中已就位的分割位置”，算法的核心是计算每个子数组需要执行的 bubble_sort_pass 次数，再乘以子数组长度求和。

二、算法原理

1. 离散化处理

由于数组元素可能重复且范围大，先对数组元素离散化：

• 将原数组元素排序去重（保留索引信息），给每个元素分配一个排名（相同元素按原索引顺序排名），得到离散化后的数组 a，其中 a[i] 表示原数组第 i 个位置元素的排名；
• 同时维护 inva 数组，inva[r] 表示排名为 r 的元素在原数组中的位置。

2. 关键变量定义

• p[i]：表示排序后数组中“前 i 个元素”与“后 n-i 个元素”的分割位置（对应原数组的分隔点）所需的最少 bubble_sort_pass 次数；
• cnt1：统计当前未满足“分隔点条件”的元素个数，用于推导 p[i]；
• lst0：追踪排名为 i 的元素在原数组中的位置，用于更新 cnt1。

3. 核心推导逻辑

排序后，前 i 个元素的排名是 1~i，后 n-i 个元素的排名是 i+1~n。一个分割位置 i 成为分隔点的条件是：所有排名 1~i 的元素在原数组中的位置都在所有排名 i+1~n 的元素之前。

bubble_sort_pass 的本质是让较大元素“向右冒泡”、较小元素“向左冒泡”。每个 bubble_sort_pass 最多让一个逆序对中的较大元素右移一位。因此，p[i] 等于“排名 1~i 的元素中，位于排名 i+1~n 元素左侧的逆序对数的最大值”，这一值可通过 cnt1 动态计算。

4. 工作量计算

最终总工作量是所有子数组的“长度 × 所需 bubble_sort_pass 次数”之和。通过 p 数组的特性，总工作量可简化为 sum(max(p[i-1], p[i]))（i 从 1 到 n），其中 p[0] = p[n] = 0。

三、完整代码

#include <bits/stdc++.h>
#define int long long
#define mkp make_pair
using namespace std;

int n, a[100005], inva[100005], p[100005];
vector<pair<int, int>> vc;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i], vc.push_back({a[i], i});
    sort(vc.begin(), vc.end());

    for (int j = 0; j < n; j++)
        a[vc[j].second] = j + 1, inva[j + 1] = vc[j].second;

    int lst0 = 0, cnt1 = 0;
    for (int i = 1; i < n; i++) {
        if (inva[i] < lst0)
            cnt1--;
        else {
            while (lst0 < inva[i]) {
                lst0++;
                if (a[lst0] > i)
                    cnt1++;
            }
        }
        p[i] = max(1ll, cnt1);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += max(p[i - 1], p[i]);
    }

    cout << ans;
    return 0;
}

四、代码关键步骤解析

1. 离散化

• 读取原数组后，将每个元素与其索引组成 pair 存入 vc，按元素值排序（相同元素按索引排序）；
• 遍历排序后的 vc，给每个原数组位置 i 分配排名 j+1（j 是排序后的索引），存入 a[i]；同时 inva[j+1] = i，记录排名对应的原位置。

2. 计算 p 数组

• 初始化 lst0 = 0（当前追踪的原数组位置）、cnt1 = 0（未满足分隔点条件的元素个数）；
• 遍历排名 i（1 到 n-1）：
  • 若排名 i 的原位置 inva[i] 小于 lst0，说明该元素已被之前的处理覆盖，cnt1 减 1；
  • 否则，将 lst0 推进到 inva[i]，途中若遇到“排名大于 i 的元素”（即属于后 n-i 个元素），则 cnt1 加 1（该元素需要被冒泡到右侧）；
  • p[i] 取 cnt1 和 1 的最大值（至少需要 1 次冒泡才能产生分隔点）。

3. 计算总工作量

• 遍历 i 从 1 到 n，累加 max(p[i-1], p[i])（p[0] 和 p[n] 默认为 0）；
• 该累加和即为总工作量，直接输出。

五、复杂度分析

• 时间复杂度：$O(N \log N)$。核心耗时为数组排序（离散化步骤），后续遍历均为 $O(N)$；
• 空间复杂度：$O(N)$。用于存储原数组、离散化数组、inva 数组、p 数组及排序用的 vector，可满足 $N \leq 10^5$ 的约束。