题目描述

暴力或者归并排序

样例

import java.util.*;
public class Main{

    /*
    暴力做法：

    核心
    统计某个数之前比这个数大的数的数量+某个数之后比这个数小的数的数量 然后用等差数列求和：n(a1+an)/2
    对于1+2+3+...+n 求和公式：(an)(an+1)/2

    static long summary(long long x){
        int k;
        k=(1+x)*x/2;
        return k;
    }

    public static void main(String[] args){
        for(int i=1;i<=n;i++){
          long res=0;
          for(int j=1;j<i;j++){
            if(a[j]>a[i]){
                res++;
            }
        }

        for(int j=i+1;j<=n;j++){
            if(a[j]<a[i]){
                res++;
            }
        }

        res=summary(res);
        num[i]=res;
        }

        for(int i=1;i<=n;i++){
          ans+=num[i];
        }

    */

    //归并排序法
    static class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;//身高
            this.y = y;//第几个小朋友
        }
    }

    static final int N = 100010;
    static int n;
    static Pair[] q = new Pair[N], tmp = new Pair[N];
    static int[] sum = new int[N];//统计该名小朋友需要交换次数

    static void merge(int l, int r) {
        if (l >= r) return;

        int mid = (l + r) >> 1;

        merge(l, mid);

        merge(mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (q[i].x <= q[j].x) {
                sum[q[i].y] += j - 1 - (mid + 1)  + 1;//加上后面比q[i]小的数的个数(操作1)
                tmp[k++] = q[i++];
            } else {
                sum[q[j].y] += mid - i + 1;//加上前面比q[j]大的数的个数(操作2)
                tmp[k++] = q[j++];
            }
        }
        //如果左边区间还有剩
        while (i <= mid) {
            //此时右边区间所有的数全都小于左边区间剩余的数，所以都加上
            sum[q[i].y] += j - 1 - (mid + 1)  + 1;//加上后面比q[i]小的数的个数
            tmp[k++] = q[i++];
        }
        //如果右边区间还有剩，剩余的数肯定都大于左边区间，与操作1、2不符，所以不像上个循环有补充操作
        //也就是没有前面比q[j]大的数了
        while (j <= r) tmp[k++] = q[j++];

        for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            q[i] = new Pair(scanner.nextInt(), i);
        }

        merge(0, n - 1);

        long res = 0;
        for (int i = 0; i < n; i++) {
            res += (long) sum[i] * (sum[i] + 1) / 2;
        }

        System.out.println(res);
    }

}