P4650 能量收集器（提高）

解题思路

先读懂题目：一列柱子从前往后排好，每一根柱子会与它后面所有「比它矮」的柱子各组成一个能量收集器，柱子可以重复使用。其实这就是在数「逆序对」：只要前面有一根柱子比后面的一根柱子高（heights[i] > heights[j]，而且 i < j），这一对就贡献一个收集器。

**第一步，读懂题意。**读入 n 根柱子的高度，统计所有满足「前面的柱子比后面的柱子高」的数对数量。这个数对的数量就是答案。

**第二步，对照样例理解。**样例是 9 7 5 8 3 10。9 后面比它矮的有 7、5、8、3，共 4 个；7 后面比它矮的有 5、3，共 2 个；5 后面比它矮的只有 3，共 1 个；8 后面比它矮的有 3，共 1 个；3 和 10 后面都没有更矮的柱子。加起来 4+2+1+1=8，正好是样例答案。

**第三步，想想为什么不能暴力统计。**n 最多 10 万，如果用两层循环一个一个数，10 万 × 10 万 = 100 亿次比较，一定会超时。所以必须用更聪明的算法。

**第四步，用归并排序统计。**把数列不断对半分，等左右两半各自排好序后合并时，如果右边的数 heights[j] 比较小，就说明左边从 heights[i] 到 heights[mid] 这一整段都比 heights[j] 大，它们全部能和 heights[j] 组成收集器，于是一次加上 mid - i + 1 个，效率极高。每一对逆序对都只会被统计一次，不会重复也不会漏掉。

**第五步，注意用 long long。**n 个数最多有 n(n-1)/2 对逆序对，10 万个数能到约 50 亿，超出了 int 的范围，所以答案变量必须用 long long 保存。

**第六步，总结优化思想。**为什么用归并排序？因为它能把「数逆序对」变成「合并时的附加动作」。两半各自排好序后，只要右边取出来的数比左边剩下的数小，左边剩下的这些数就全都比它大，一次就能数出一大片，时间复杂度从 O(n²) 降到了 O(n log n)。这就是算法优化的意义：同样的答案，换一种更聪明的做法，速度天差地别。

参考代码

// P4650 能量收集器：统计逆序对数量（每根柱子与后面比它矮的柱子组成收集器）
#include <iostream>
using namespace std;

int heights[100005]; // 每根柱子的高度
int temp[100005];    // 归并时使用的临时数组
long long count;     // 能量收集器总数（逆序对数量）

// 归并排序，排序的同时统计逆序对
void msort(int left, int right) {
    if (left >= right) return; // 区间里只有一根柱子时已经有序
    int mid = (left + right) / 2; // 把区间分成左右两半
    msort(left, mid); // 排序左半部分
    msort(mid + 1, right); // 排序右半部分
    int i = left; // 左半部分当前下标
    int j = mid + 1; // 右半部分当前下标
    int k = left; // 临时数组当前下标
    while (i <= mid && j <= right) { // 两边都还有柱子时比较
        if (heights[i] <= heights[j]) { // 左边柱子更矮，不会形成逆序对
            temp[k++] = heights[i++]; // 把左边柱子放入临时数组
        } else {
            // 左边剩下的柱子都比heights[j]高，都能与它组成收集器
            count += mid - i + 1;
            temp[k++] = heights[j++]; // 把右边柱子放入临时数组
        }
    }
    while (i <= mid) temp[k++] = heights[i++]; // 放入左边剩余柱子
    while (j <= right) temp[k++] = heights[j++]; // 放入右边剩余柱子
    for (i = left; i <= right; i++) heights[i] = temp[i]; // 复制回原数组
}

int main() {
    int n; // 柱子数量
    cin >> n; // 读入柱子数量
    for (int i = 0; i < n; i++) cin >> heights[i]; // 读入每根柱子的高度
    count = 0; // 逆序对数量清零
    msort(0, n - 1); // 统计整个数列的逆序对
    cout << count << endl; // 输出能量收集器总数
    return 0;
}

复杂度分析

归并排序每次把区间一分为二，递归深度大约是 log2(n)；每一层合并时，每个元素都只被移动一次。所以总时间 O(n log n)，空间上需要一个与数组等长的临时数组 temp，是 O(n)。n 最大 10 万时，log2(10万)≈17，运算量大约 170 万次，轻松通过时间限制。