题解 | #逆序对#

1. 注意，一个序列的正序对+逆序对永远是常数。
2. 最后输出整个逆序对的结果。
3. index最后一层必为1；
4. 交换的时候顺序对每pow（2，x）交换其实就是预先构建好的正序对交换到逆序对上，然后对逆序对求和。

#include<bits/stdc++.h>
using namespace std;

void merge(int arr[],int left,int mid,int right,int index,vector<long>& reorder){
    vector<int> temp(right-left+1,0);
    int i = left, j = mid+1, k = 0, origin = left;
    long c =0 ; 
    while(i<=mid&&j<=right){
        if(arr[i]<=arr[j]){//必须小于等于，因为下一个条件是给逆序对的。
            temp[k++] = arr[i++];
        }else{
            temp[k] = arr[j];
            c+= mid+1 - i;//加和逆序对的个数
            k++;
            j++;
        }
    }

    for(;i<=mid;){
        temp[k++] = arr[i++];
    }

    for(;j<=right;){
        temp[k++] = arr[j++];
    }

    // 将临时数组中的元素放入到原数组的指定位置
    for(auto num:temp){
        arr[origin++] = num;
    }

    reorder[index] +=c;//最后赋值 //逆序对个数
}


void mergesort(int arr[],int left, int right,vector<long>& reorder,int index){
    int mid = (left+right)/2;

    if(left<right){
        mergesort(arr,left,mid,reorder,index-1);
        mergesort(arr,mid+1,right,reorder,index-1);
        merge(arr,left,mid,right,index,reorder);
    }
}




int main(){
    int n,m;
    cin>>n;
    long x;
    vector<long> v,q;

    int N = 1<<n;

    //正序数组
    int a[N];
    //逆序数组
    int b[N];


/*
            order[i] 表示 2^i 的 顺序对个数
            reOrder[i] 表示 2^i 的 逆序对个数

            比如 i = 1，那么就是每 2 个元素的逆序对的个数，比如 [4,3,2,1]，
            有 [2,1] [4,3] 两个逆序对，即 reOrder[1] = 2

            比如 i = 2，那么就是每 4 个元素的逆序对的个数，比如 [4,3,2,1], 
            有 [4,3] [2,1] [4,2] [4,1] [3,2] [3,1] 6 个逆序对，
            只不过 [2,1] [4,3] 在 i = 1 的时候算过了，因此有 4 个
            即 reOrder[2] = 4


            我们可以发现，如果大小为 n 的数组是降序的，
            那么逆序对个数为 n * (n - 1) / 2 个
            比如 [4,3,2,1] 
            对于 4 来说，后面有 [3,2,1] 3 个元素小于它，那么逆序对个数为 3
            对于 3 来说，逆序对个数为 2
            对于 2 来说逆序对个数为 1
            如果数组是降序的,那么逆序对个数为 
            (n - 1) + (n - 2) + ... + 1
           = n * (n - 1) / 2
            而顺序对的个数为 0，但如果我们将其中两个元素交换位置，
            减少了 m 个逆序对的同时就会增加 m 个顺序对
            这表示 顺序对的个数 + 逆序对的个数 = n * (n - 1) / 2，
            即 顺序对 和 逆序对 是互补的

            或者这么说，当数组的逆序对个数为 m， 顺序对的个数为 n
            那么数组翻转过后，逆序对和顺序对的个数相互交换
            即逆序对的个数变为 n， 顺序对的个数变为 m

            因此，当我们对 2^i 个元素进行翻转的时候
            实际上就是交换它们的顺序对和逆序对个数
         */
     // order[i] 表示 2^i 的 顺序对个数
    //reOrder[i] 表示 2^i 的 逆序对个数

    vector<long> order(N+1,0);
    vector<long> reorder(N+1,0);


    for(int i =0; i< N;i++){
        cin>>x;
        a[i] = x;//正向添加
        b[N-1-i] = x;//反向添加
    }
    //一次归并求逆序对数
    mergesort(a,0,N-1,reorder,n);
    //一次归并求顺序对数(逆着求逆序对得个数，那就是顺序对得个数)
    mergesort(b,0,N-1,order,n);


    cin>>m;
    for(int i =0; i< m;i++){
        cin>>x;
        // 2^i 个元素为一组进行翻转(0不需要翻转)
        for(int j =1; j<=x;j++){
            swap(order[j],reorder[j]);
        }

        long count = 0;
        for(int k =1;k<=n;k++){
            count+=reorder[k];
        }
        cout<<count<<endl;

    }
}