题解 | #计算数组的小和#

// 按照左神的思路写的 
// https://www.bilibili.com/video/BV1L14y1B7ef/?spm_id_from=trigger_reload&vd_source=8ea6dc6c02215b66383cf6ab9791e3b4
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

std::vector<int> nums;
std::vector<int> helps;
int64_t data_merge(int left, int mid, int right)
{
    if (left == right) {
        return 0;
    }
    // 计算左跨右的子和, 一个一个计算右区的元素还要增加多少个子和
    // 已知左区和右区都排序好了
    int64_t sum = 0; // 记录i位置前面元素的和（类似前缀合）
    int64_t res = 0;
    for (int i = left, j = mid + 1; j <= right; ++j) {
        // i 就是第一次比 j大的元素下标，或者已经超出左区范围了
        while (i <= mid && nums[i] <= nums[j]) {
            sum += nums[i++];
        }
        res += sum; // j 元素要添加的子和（也就是i元素之前的子和）
    }

    // 下面是归并排序
    int i = left;
    int j = mid + 1;
    int star = left;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            helps[star++] = nums[i++];
        } else {
            helps[star++] = nums[j++];
        }
    }

    while (i <= mid) {
        helps[star++] = nums[i++];
    }

    while (j <= right) {
        helps[star++] = nums[j++];
    }

    for (int i = left; i <= right; ++i) {
        nums[i] = helps[i];
    }
    return res;
}

int64_t recursion(int left, int right)
{
    if (left == right) {
        // 没有子和
        return  0;
    }

    int mid = left + ((right - left) >> 1);
    int64_t sum = recursion(left, mid) + recursion(mid + 1, right);
    return  sum + data_merge(left, mid, right);
}

int main() {
    int n;
    std::cin >> n;
    nums.resize(n);
    helps.resize(n);
    for (int i = 0; i < n; i++) {
        int val;
        std::cin >> val;
        nums[i] = val;
    }
    int64_t ret = recursion(0, n - 1);
    std::cout << ret << std::endl;
}
// 64 位输出请用 printf("%lld")