背模板

C++ 代码

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int q[N], t[N];
LL swap_m(int l , int r)
{
    if(l >= r)  return 0;
    int mid = l + r >> 1;
    LL res = swap_m(l, mid) + swap_m(mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(q[i] <= q[j])    t[k++] = q[i++];
        else
        {
            t[k++] = q[j++];
            res += mid - i + 1;
        }
    while(i <= mid) t[k++] = q[i++];
    while(j <= r)   t[k++] = q[j++];
    for(i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
    return res;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)  cin >> q[i];
    cout << swap_m(0, n - 1);
    return 0;
}

Java 代码

import java.util.Scanner;
public class Main
{
    static int N = 1000010;
    static int q[] = new int [N];
    public static void main(String[] args)
    {
        Scanner get = new Scanner(System.in);
        int n = get.nextInt();
        for(int i = 0; i < n; i++)  q[i] = get.nextInt();
        System.out.println(swap_m(0, n - 1));
    }
    public static long swap_m(int l, int r)
    {
        if(l >= r)  return 0;
        int mid = l + r >> 1;
        long res = swap_m(l, mid) + swap_m(mid + 1, r);
        int t[] = new int [r - l + 1];
        int k  =0, i = l, j = mid + 1;
        while(i <= mid && j <= r)
            if(q[i] <= q[j])    t[k++] = q[i++];
            else
            {
                t[k++] = q[j++];
                res += mid - i + 1;
            }
        while(i <= mid) t[k++] = q[i++];
        while(j <= r)   t[k++] = q[j++];
        for(i = l, j = 0; i <= r; i++, j++) q[i] = t[j];
        return res;
    }
}