题解 | #逆序对#

1. 反转加计算
   只能过40%

import java.util.Scanner;
import java.util.*;
import java.io.*;


public class Main{
    public static void main(String[] args) {

        Scanner sc = new Scanner(new BufferedInputStream(System.in));

        int n = sc.nextInt();
        int len = (int)Math.pow(2,n);
        int[] arr = new int[len];
        for(int i=0;i<len;i++){
            arr[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        int[] swap_n = new int[m];
        for(int i=0;i<m;i++){
            //反转数组
            int fac = (int) Math.pow(2,sc.nextInt());
            for (int j=0;j<len/fac;j++){
                if(fac == 1) break;
                for(int k=0; k< fac/2 ;k++){
                    int tempnum = arr[k+ j*fac];
                    arr[k+ j*fac] = arr[(j+1)*fac-1-k];
                    arr[(j+1)*fac-1-k] = tempnum;
                }
            }
            //克隆不能忘  因为merg会把数组排序
            int[] newarr = arr.clone();
            // 归并 逆序对
            int out = mergesort(0,arr.length-1,newarr);
            System.out.println(out);
        }


    }
    static void reverse(int a[])
    {
        Collections.reverse(Arrays.asList(a));
        System.out.println(Arrays.asList(a));
    }
    static int mergesort(int l, int r, int[] arr){
        if(l>=r) return 0;

        int mid = (l+r)/2;

        int a = mergesort(l,mid,arr);
        int b = mergesort(mid+1,r,arr);

        int i=l;
        int j = mid+1;
        int res= 0;

        int[] temp = new int[arr.length];
        for(int k=l;k<=r;k++){
            temp[k] = arr[k];
        }
        for(int k=l;k<=r;k++){
            if(i == mid+1) {
                arr[k] = temp[j++];
            }
            else if(j==r+1){
                arr[k] = temp[i++];
            }
            else if(temp[j] > temp[i]){
                arr[k] = temp[i++];
            }
            else{
                res = res+ mid +1 -i;
                arr[k] = temp[j++];
            }
        }


        return res + a +b;
    }

}