首页 > 试题广场 >

逆序对

[编程题]逆序对
  • 热度指数:5775 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
作为程序员的小Q,他的数列和其他人的不太一样,他有个数。
老板问了小Q一共 m次,每次给出一个整数, 要求小Q把这些数每分为一组,然后把每组进行翻转,小Q想知道每次操作后整个序列中的逆序对个数是多少呢?

例如:
对于序列1 3 4 2,逆序对有(4, 2),(3, 2),总数量为2。
翻转之后为2 4 3 1,逆序对有(2, 1),(4, 3), (4, 1), (3, 1),总数量为4。

输入描述:
第一行一个数
第二行个数,表示初始的序列()
第三行一个数
第四行m个数表示


输出描述:
m行每行一个数表示答案。
示例1

输入

2
2 1 4 3
4
1 2 0 2

输出

0
6
6
0

说明

初始序列2 1 4 3
2^{q_1} = 2 ->
第一次:1 2 3 4 -> 逆序对数为0
2^{q_2} = 4 ->
第二次:4 3 2 1 -> 逆序对数为6
2^{q_3} = 1 ->
第三次:4 3 2 1 -> 逆序对数为6
2^{q_4} = 4 ->
第四次:1 2 3 4 -> 逆序对数为0
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = 1<<n;
        int[] a = new int[k];
        int[] b = new int[k];
        for(int i=0;i<k;i++){
            a[i] = sc.nextInt();
            b[k-1-i] = a[i];
        }
        int m = sc.nextInt();
        int[] q = new int[m];
        for(int i=0;i<m;i++){
            q[i] = sc.nextInt();
        }
        getAns(n,a,b,m,q);
    }

    public static void getAns(int n,int[] a,int[] b,int m,int[] q){
        int k = a.length;
        int[] tmp = new int[k];
        long[] reorder = new long[n+1];
        long[] order = new long[n+1];
        reverse(a,0,k-1,reorder,tmp,n);
        reverse(b,0,k-1,order,tmp,n);
        for(int i=0;i<m;i++){
            int cur = q[i];
            for(int j=1;j<=cur;j++){
                long temp = reorder[j];
                reorder[j] = order[j];
                order[j] = temp;
            }
            long count = 0;
            for(int j=1;j<=n;j++){
                count+=reorder[j];
            }
            System.out.println(count);
        }
    }

    public static void reverse(int[] arr,int left,int right,long[] reorder,int[] tmp,int index){
        if(left<right){
            int mid = (left+right)>>>1;
            reverse(arr,left,mid,reorder,tmp,index-1);
            reverse(arr,mid+1,right,reorder,tmp,index-1);
            if(arr[mid]>arr[mid+1])
                reverseCross(arr,left,mid,right,reorder,tmp,index);
        }
    }

    public static void reverseCross(int[] arr,int left,int mid,int right,long[] reorder,int[] tmp,int index){
        for(int i=left;i<=right;i++){
            tmp[i] = arr[i];
        }
        int i = left,j = mid+1;
        long count = 0;
        for(int k=left;k<=right;k++){
            if(i==mid+1){
                arr[k] = tmp[j];
                j++;
            }else if(j==right+1){
                arr[k] = tmp[i];
                i++;
            }else if(tmp[i]<=tmp[j]){
                arr[k] = tmp[i];
                i++;
            }else if(tmp[i]>tmp[j]){
                arr[k] = tmp[j];
                j++;
                count+=mid-i+1;
            }
        }
        reorder[index] += count;
    }
}

发表于 2020-08-20 21:30:38 回复(0)
/* 段错误:您的程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多)等情况引起case通过率为0.00% */
//有没有大佬指正下

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int main() {
    int n, N, m;
    int qi[20];

    cin >> n;

    N = pow(2, n);
    vector<int> x(N);
    for (int i = 0; i <N ; i++) {
        cin >> x[i];
    };

    cin >> m;
    for (int i = 0; i <m; i++) {
        cin >> qi[i];
    };

    for (int i = 0; i <m; i++) {

        //翻转
        int b = pow(2, qi[i]);  //一组多少个数
        int a = N /b;  //分成了多少组
        //每一组进行翻转
        for (int j = 0; j < a; j++) {
            int temp;
            for (int k = 0; k <b/2; k++) {
                temp = x[k + j*b];
                x[k + j*b] = x[j*b + b - 1 - k];
                x[j*b + b - 1 - k] = temp;
            };
        };

        //逆序对
        int p=0;
        for (int j = 0; j < N-1; j++) {
            for (int k = j+1; k < N; k++) {
                if (x[j] > x[k])p++;
            };
        };
        qi[i] = p;
    };

    for (int i = 0; i < m; i++) {
        cout << qi[i] << " ";
    };

    system("pause");
}

编辑于 2020-05-14 01:08:35 回复(0)
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int N = 1 << n;
        //正序数组
        int[] a = new int[N];
        //逆序数组
        int[] b = new int[N];
        long[] order = new long[n + 1];
        long[] reOrder = new long[n + 1];
        for (int i = 0; i < N; ++i) {
            //正序添加元素
            a[i] = sc.nextInt();
            //倒序添加元素
            b[N - 1 - i] = a[i];
        }
        int[] tmp = new int[N];
        //一次归并求逆序对数
        mergeCount(a, 0, N - 1, tmp, reOrder, n);
        //一次归并求顺序对数
        mergeCount(b, 0, N - 1, tmp, order, n);

        int m = sc.nextInt();
        while (m-- > 0) {
            // 2^i 个元素为一组进行翻转
            int q = sc.nextInt();
            for (int i = 1; i <= q; ++i) {
                long temp = order[i];
                order[i] = reOrder[i];
                reOrder[i] = temp;
            }
            long count = 0;
            for (int i = 1; i <= n; ++i) {
                count += reOrder[i];
            }
            System.out.println(count);
        }
    }
    private static void mergeCount(int[] nums, int left, int right, int[] temp, long[] reOrder, int index) {
        if (left >= right) return;
        int mid = (left + right) >>> 1;
        mergeCount(nums, left, mid, temp, reOrder, index - 1);
        mergeCount(nums, mid + 1, right, temp, reOrder, index - 1);
        int i = left, j = mid + 1;

        while (i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                reOrder[index] += (mid + 1 - i);
                ++j;
            } else {
                ++i;
            }
        }
        merge(nums, left, mid, right, temp);
    }

    private static void merge(int[] nums, int left, int mid, int right, int[] temp) {
        System.arraycopy(nums, left, temp, left, right - left + 1);
        int i = left, j = mid + 1, k = left;

        while (i <= mid && j <= right) nums[k++] = temp[i] <= temp[j] ? temp[i++] : temp[j++];
        while (i <= mid) nums[k++] = temp[i++];
        while (j <= right) nums[k++] = temp[j++];
    }
}
发表于 2020-09-22 17:43:16 回复(0)
O(nlogn)可全过
大概思路就是记录所有2^i上的逆序对,只要记录2i-1和另一半2i-1之间的逆序对,例如2341里面
21上有1个
22上一共3个,但是有一个在21中算过了,所以就是2个
计算这个值的过程用O(n2)能过80%,改成merge可以全过
同时,要计算2i下所有可能的组合,即2i-1*2i-1,再乘上2i的个数,即2n-i,得到2n+i-2,在merge的过程中同时还要记录等于的情况,因为这些等于的不管是否翻转都不是逆序对,所以对每一个2i还要减去等于的对数。
然后翻转的时候,假如翻转数字的是x,对于每个2i(x >= i),值都改为上面求出的数 - 原值
逆序对总数就是从1-n求和。
#include<stdio.h>
#include<vector>
using namespace std;

long long n, m, total, sum, offset, num;

vector<long long> count;
vector<long long> l;
vector<long long> l_copy;
vector<long long> max_c;
void mergesort(long long index, long long size)
{
    if(size == 0)
    {
    	l_copy[index] = l[index];
    	return;
	}
    vector<long long> l_copy2(1<<size);
	long long st1 = index, st2 = index + (1 << (size - 1) ), ed1 = st2, ed2 = index + (1 << size);
    long long pos = 0, p1 = st1, p2 = st2;
    mergesort(st1, size - 1);
    mergesort(st2, size - 1);
    while(p1 < ed1 && p2 < ed2)
    {
        if(l_copy[p1] == l_copy[p2]){
            long long c1 = 1, c2 = 1;
            l_copy2[pos++] = l_copy[p1++];
            l_copy2[pos++] = l_copy[p2++];
            while(p1 < ed1 && l_copy[p1] == l_copy[p1 - 1]) l_copy2[pos++] = l_copy[p1++], ++c1; 
            while(p2 < ed2 && l_copy[p2] == l_copy[p2 - 1]) l_copy2[pos++] = l_copy[p2++], ++c2;
            max_c[size] -= c1 * c2;
            count[size] += (ed1 - p1) * c2;
        }
        else if(l_copy[p1] < l_copy[p2]){
            l_copy2[pos++] = l_copy[p1++];
        }
        else {
            count[size] += ed1 - p1;
            l_copy2[pos++] = l_copy[p2++];
        }
    }
    if(p1 == ed1)while(p2 != ed2) l_copy2[pos++] = l_copy[p2++];
    else if(p2 == ed2) while(p1 != ed1) l_copy2[pos++] = l_copy[p1++];
    for(long long i = st1; i < ed2; ++i) l_copy[i] = l_copy2[i - st1]; 
}

int main()
{   
	scanf("%lld", &n);
	total = (long long)1 << n;
    count.resize(n + 1);
    max_c.resize(n + 1);
    l.resize(total);
    l_copy.resize(total);
	for(long long i = 0; i < total; ++i) scanf("%lld", &l[i]);
	max_c[0] = 1;
	for(long long i = 1; i <= n; ++i) max_c[i] = (long long)1 <<(n + i  - 2);//(1 << 2 * (i - 1) ) * ( 1 << (n - i))
	
    mergesort(0, n);
    
	scanf("%lld", &m);
	for(long long i = 0; i < m; ++i)
	{
		scanf("%lld", &num);
		sum = 0;
		for(long long j = 1; j <= n; ++j)
		{
			if(j <= num) count[j] = max_c[j] - count[j];
			sum += count[j];
		}
		printf("%lld\n", sum);
	}
}


编辑于 2020-04-11 14:46:40 回复(7)
思路差不多就这样,如果注释哪里写错了欢迎指正
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int N = 1 << n;
        //正序数组
        int[] a = new int[N];
        //a 的逆序数组,比如 a = [4,3,2,1], b = [1,2,3,4]
        int[] b = new int[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 个元素进行翻转的时候
            实际上就是交换它们的顺序对和逆序对个数
         */
        long[] order = new long[n + 1];
        long[] reOrder = new long[n + 1];
        for (int i = 0; i < N; ++i) {
            //正序添加元素
            a[i] = sc.nextInt();
            //倒序添加元素
            b[N - 1 - i] = a[i];
        }
        //一次归并求逆序对数
        mergeSort(a, 0, N - 1, reOrder, n);
        //一次归并求顺序对数
        mergeSort(b, 0, N - 1, order, n);

        int m = sc.nextInt();
        while (m-- > 0) {
            // 2^i 个元素为一组进行翻转
            int q = sc.nextInt();
            for (int i = 1; i <= q; ++i) {
                long temp = order[i];
                order[i] = reOrder[i];
                reOrder[i] = temp;
            }
            long count = 0;
            for (int i = 1; i <= n; ++i) {
                count += reOrder[i];
            }
            System.out.println(count);
        }
    }
    private static void mergeSort(int[] arr, int left, int right, long[] reOrder, int index){
        if(left < right){
            int mid = (left + right) >>> 1;
            //归并使得 左右两边保证有序
            mergeSort(arr, left, mid, reOrder, index - 1);
            mergeSort(arr, mid + 1, right, reOrder, index - 1);
            if(arr[mid] > arr[mid + 1]){
                mertSort(arr, left, right, mid, reOrder, index);
            }
        }
    }
    public static void mertSort(int[] arr, int left, int right, int mid, long[] reOrder, int index) {
        //mid 属于左边
        int len1 = mid - left + 1;
        int len2 = right - mid;

        int[] l = new int[len1];
        int[] r = new int[len2];
        System.arraycopy(arr, left, l, 0, len1);
        System.arraycopy(arr, mid + 1, r, 0, len2);

        /*
        逆序对:l[i] > r[j]
        [left, mid) 是有序的,[mid, right] 是有序的
        因此,如果 l[i] > r[j],表示 l[i] 比 [0, j] 这些元素都大
        那么逆序对个数对于 l[i] 来说,有 j + 1个
        */
        int i = len1 - 1;
        int j = len2 - 1;
        int k = right;
        long c = 0;
        while(i >= 0 && j >= 0){
            if(l[i] > r[j]){
                c += j + 1;
                arr[k] = l[i];
                i--;
            }else{
                arr[k] = r[j];
                j--;
            }
            k--;
        }
        System.arraycopy(r, 0, arr, left, j + 1);

        //逆序对个数
        reOrder[index] += c;
    }
}


发表于 2020-08-28 11:55:41 回复(6)
cdf头像 cdf
通过百分之百,先利用归并排序初始化不同间隔的逆序对和顺序对之和,当反转时交换顺序对和逆序对即可。每次查询时将不同间隔的逆序对加起来。总复杂度为O(nm+n*2^n)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1<<20)+50;;
int n,m,q[maxn],a[maxn],v1[maxn],v2[maxn];
ll rev[50],nor[50];
void init(int o,int l,int r,ll rev[],int nums[]){
    if(r==l){
        return;
    }
    int mid=(l+r)/2;
    init(o-1,l,mid,rev,nums);
    init(o-1,mid+1,r,rev,nums);
    ll no=0,re=0;
    int i=l,j=mid+1,k=l;
    for (i=l,j=mid+1,k=l;i<=mid && j<=r;){
        if(nums[i]<=nums[j]){
            a[k++]=nums[i];
            i++;
        }
        else{
            a[k++]=nums[j];
            re+=1L*mid+1-i;
            j++;
        }
    }
    if(i<=mid){
        while (i<=mid){
            a[k++]=nums[i++];
        }
    }
    if(j<=r){
        while (j<=r){
            a[k++]=nums[j++];
        }
    }
    rev[o]+=re;
    for (i=l;i<=r;i++){
        nums[i]=a[i];
    }
 
}
 
ll solve(int o){
    for (int i=o;i>=0;i--){
        swap(nor[i],rev[i]);
    }
    ll ans=0;
    for (int i=0;i<=n;i++){
        ans+=rev[i];
    }
    return ans;
}
 
int main(){
    cin>>n;
    int temp;
    //vector<int> v1,v2;
    for (int i=0;i<(1<<n);i++){
        scanf("%d",&temp);
        v1[i]=temp;
        v2[i]=temp;

    }
    cin>>m;
    for (int i=0;i<m;i++){
        scanf("%d",&q[i]);
    }
    memset(nor,0,sizeof(nor));
    memset(rev,0,sizeof(rev));
    init(n,0,(1<<n)-1,rev,v1);
    reverse(v2,v2+(1<<n));
    init(n,0,(1<<n)-1,nor,v2);

    for (int i=0;i<m;i++){
        cout<<solve(q[i])<<endl;
    }
}


发表于 2020-03-04 17:30:23 回复(3)
cqz头像 cqz
这题的坑很多,我的通过率从50 到10 到60 到70 到80 到100.。。。主要是要求解不同长度的逆序对和顺序对数量,翻转后将相应的进行交换,注意相等的情况(既不是逆序对也不是顺序对,可以求解翻转后的数组的逆序对来得到原数组的顺序对)。
详情可以参考我的博客。
发表于 2020-04-04 18:03:30 回复(2)

求逆序对问题用归并排序的时间复杂度比暴力算法更低。

假设有一个数组{8,1,2,5,7,4,3,6}

首先归并排序第一次对数组进行分割      8 1 2 5      7 4 3 6

                         二次分割      8 1      25      74      36

                         三次分割      8      1      2      5      7      4      3      6      

                      第一次合并     18     25     47     36      reorder[1]=2, order[1]=2               

 //用reorder[i]来记录第i次合并中存在的逆序对数,order[i]来记录第i次合并中存在的顺序对数。

                      第二次合并     1258     3467     reorder[2]=5, order[2]=3

                      第三次合并     12345678          reorder[3]=6, order[3]=10

那么数组{8,1,2,5,7,4,3,6}中存在的逆序对就等于reorder[1]+reorder[2]+reorder[3]=13

 

将数组{8,1,2,5,7,4,3,6}每2^2个为一组进行翻转{5,2,1,8,6,3,4,7}

首先归并排序第一次对数组进行分割      5 2 1 8      6 3 4 7

                         二次分割      5 2      18      63      47

                         三次分割      5      2      1      8      6     3      4      7      

                      第一次合并     25     18    36     47      reorder[1]=2, order[1]=2 

                      第二次合并     1258     3467     reorder[2]=3, order[2]=5

                      第三次合并     12345678          reorder[3]=6, order[3]=10

那么数组{5,2,1,8,6,3,4,7}中存在的逆序对就等于reorder[1]+reorder[2]+reorder[3]=11

由此我们可以观察到对数组每2^2个进行翻转时,reorder[1]和order[1]进行了互换,reorder[2]和order[2]亦是如此。

所以对数组每2^i个进行翻转时,我们可以把1~i的reorder和order数组元素互换即可继续通过计算reorder数组的累加和来求得数组的逆序对数。

import java.util.ArrayList;
import java.util.Scanner;

public class Main {


        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int N = 1 << n;
            int[] a = new int[N];
            int[] b = new int[N];//用来存储数组的逆序,对逆序的数组进行一次归并排序可以直接得到order数组
            int[] order = new int[n + 1];//为了便于计算,所以设置order下标是1~n,因此数组大小为n+1
            int[] reorder = new int[n + 1];
            for (int i = 0; i < N; i++) 
            {
                a[i] = sc.nextInt();
                b[N - i - 1] = a[i];
            }
            MergeSort(a, 0, N - 1, reorder, n);//对整个数组进行归并排序,n表示对reorder[1]~reorder[n]进行初始化
            MergeSort(b, 0, N - 1, order, n);//对整个逆序数组进行归并排序,完成对order[1]~order[n]的初始化
            int m = sc.nextInt();
           while(m-- > 0)
           {
               int count = 0;
               int q = sc.nextInt();
               for (int i = 1; i <= q; i++) //像之前讲的,将1~q的reorder[i]和order[i]进行互换
               {
                int temp = reorder[i];
                reorder[i] = order[i];
                order[i] = temp;
               }
               for (int i = 1; i <= n; i++) 
               {
                count+= reorder[i];//累加reorder数组,求得对数组中每2^q个元素进行翻转后的逆序对数
               }
               System.out.println(count);
           }
        }
        public static void MergeSort(int[] a , int left, int right, int[] reorder, int index)
        {
            if(left < right)
            {
                int mid = (right + left) / 2;
                MergeSort(a, left, mid, reorder,index - 1);
                MergeSort(a, mid + 1, right, reorder,index -1);
                if(a[mid] > a[mid+1])//如果a[mid]<=a[mid+1],则原数组有序,不需要合并
                Merge(a, left, right,reorder, index);
            }
        }
        public static void Merge(int[] a, int left, int right,int[] reorder, int index)//index表示对reorder[index]进行初始化
        {
            int mid = (right + left) / 2;
            int Length1 = mid - left + 1;
            int Length2 = right - mid;
            int[] l = new int[Length1];//存储a[left]~a[mid]
            int[] r = new int[Length2];//存储a[mid+1]~a[right]
            System.arraycopy(a, left, l, 0, Length1);//对l进行初始化
            System.arraycopy(a, mid + 1, r, 0, Length2);//对r进行初始化
            int i = 0;
            int j = 0;
            int c= 0;
            int k = left;
            while(i < Length1 && j < Length2)
            {
                if(l[i] <= r[j])
                {
                    a[k] = l[i];
                    i++;

                }
                else
                {
                    a[k] = r[j];
                    j++;
                    c += Length1 - i;//当l[i]>r[j]时,因为l是递增序列,所以l[i]~l[Length1-1]均>r[j],所以有Length1-i个元素大于r[j]
                }
                k++;
            }
            System.arraycopy(l, i, a, k, Length1 - i);//前面归并排序MergeSort中调用Merge合并的条件是a[mid]>a[mid+1],因为当a[mid]<=a[mid+1]时说明原数组有序,无需合并。l[Length1-1]>r[Length2-1],即l数组的最大值大于r数组的最大值,所以当r中的数全部进入a数组后,l数组中仍有剩余。
            reorder[index] += c;
        }
                        

}


编辑于 2021-03-31 18:01:39 回复(2)
考虑翻转,其实每个块内翻转不影响其它块。只需要预先统计每层的单独块内的正逆序对数(记得把非正非逆的不要算,所以就长了两个分治,丑懒得改)。然后询问对于一个块大小的翻转实际对更小的块也翻转了,直接一路异或下去即可,然后只要为0说明这个块大小没翻转过,答案就是逆序对数,否则正序对数。
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
using ll=long long;

int main() {
    int n; cin>>n;
    vector<ll>a((1<<n)+1);
    for(int i=1;i<=1<<n;i++)cin>>a[i];
    vector<ll>f(n+1),g(n+1),c((1<<n)+1),b(a);
    auto divide=[&](auto divide,int l,int r,int dep)->void{
        if(l==r)return;
        int mid=l+r>>1;
        divide(divide,l,mid,dep-1);
        divide(divide,mid+1,r,dep-1);
        int i=l,j=mid+1,k=l;
        while(i<=mid&&j<=r)
        {
            if(a[i]<=a[j])c[k++]=a[i++];
            else c[k++]=a[j++],f[dep]+=mid-i+1;
        }
        while(i<=mid)c[k++]=a[i++];
        while(j<=r)c[k++]=a[j++];
        for(int k=l;k<=r;k++)a[k]=c[k];
    };
    divide(divide,1,1<<n,n);

    a=b;
    auto divide1=[&](auto divide1,int l,int r,int dep)->void{
        if(l==r)return;
        int mid=l+r>>1;
        divide1(divide1,l,mid,dep-1);
        divide1(divide1,mid+1,r,dep-1);
        int i=l,j=mid+1,k=l;
        while(i<=mid&&j<=r)
        {
            if(a[i]<a[j])c[k++]=a[i++],g[dep]+=r-j+1;
            else c[k++]=a[j++];
        }
        while(i<=mid)c[k++]=a[i++];
        while(j<=r)c[k++]=a[j++];
        for(int k=l;k<=r;k++)a[k]=c[k];
    };
    divide1(divide1,1,1<<n,n);
    
    vector<int>d(n+1);
    int m; cin>>m;
    while(m--)
    {
        int q; cin>>q;
        ll ans=0; 
        for(int i=n;i>=1;i--)
        {
            if(i<=q)d[i]^=1;
            if(d[i])ans+=g[i];
            else ans+=f[i];
        }
        cout<<ans<<"\n";
    }
    return 0;
}


发表于 2023-03-20 02:46:05 回复(0)
归并解法,写的有点乱,修修补补的,接下来尝试一下线段树解法,主要就是记录顺序对和逆序对的数量,比如0~3,翻转0~1、2~3时,前两个和后两个之间的逆序对,顺序对不变
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> tmp;
vector<pair<ll,ll>> res;

void merge(vector<int>& data, int l, int r)
{
	if (l == r)    return;
	int mid = (l + r) >> 1;
	merge(data, l, mid);
	merge(data, mid + 1, r);
	int i = l, j = mid + 1, pos = l;
	int step = r - l + 1, exp = 0;
	while ((1 << exp) != step)	++exp;

	while (i <= mid && j <= r)
	{
		if (tmp[i] > tmp[j])
		{
			data[pos++] = tmp[i++];
			res[exp].first += r - j + 1;
		}
		else if (tmp[i] < tmp[j])
		{
			data[pos++] = tmp[j++];
			res[exp].second += mid - i + 1;
		}
		else
		{
			int val = tmp[i];
			int ii = i, jj = j;
			while (ii <= mid)
			{
				if (tmp[ii] == val) data[pos++] = tmp[ii++];
				else break;
			}
			while (jj <= r)
			{
				if (tmp[jj] == val)	data[pos++] = tmp[jj++];
				else break;
			}
			res[exp].first += (r - jj + 1)*(ii - i);
			res[exp].second += (mid - ii + 1)*(jj - j);
			i = ii, j = jj;
		}
	}
	while (i <= mid)
		data[pos++] = tmp[i++];
	while (j <= r)
		data[pos++] = tmp[j++];
	while (l <= r)
	{
		tmp[l] = data[l];
		++l;
	}
}

int main()
{
	int n, m;
	cin >> n;
	long long num = pow(2, n);
	vector<int>	numList(num);
	for (int i = 0; i < num; ++i)
		cin >> numList[i];
	tmp = numList;
	res.resize(n + 1, { 0,0 });
	merge(numList, 0, num - 1);
	cin >> m;
	int q;
	for (int i = 0; i < m; ++i)
	{
		cin >> q;
		ll ret = 0;
		for (int j = 1; j <= q; ++j)
		{
			swap(res[j].first, res[j].second);
			ret += res[j].first;
		}
		for (int j = q + 1; j <= n; ++j)
			ret += res[j].first;
		cout << ret << endl;
	}
	return 0;
}	


发表于 2020-05-07 15:59:27 回复(0)
//为什么我只能过60% 我写的有什么问题?
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using gg=long long;

void sort(vector<gg>&a,vector<gg>&tmp,vector<gg>&reord,vector<gg>&ord,gg l,gg r,gg id)
{
    if(r==l){
        return;
    }
    gg mid=l+((r-l)>>1);
    sort(a,tmp,reord,ord,l,mid,id-1);
    sort(a,tmp,reord,ord,mid+1,r,id-1);
    gg i=l,j=mid+1,k=0;
    while(i<=mid && j<=r)
    {
        if(a[i]>a[j])
        {
            reord[id]+=mid-i+1;
            tmp[k++]=a[j++];
        }else {
            ord[id]+=r-j+1;
            tmp[k++]=a[i++];
        }
    }
    
    while(i<=mid)
    {
        tmp[k++]=a[i++];
    }     
    while(j<=r)
    {
        tmp[k++]=a[j++];
    }      
    for(gg i=l,k=0;i<=r;i++)
    {
        a[i]=tmp[k++];
    }
}

int main() {
    gg N;
    cin>>N;
    gg n=1<<N;
    vector<gg>a(n);
    for(gg i=0;i<n;i++)
    {
        cin>>a[i];
    }
    vector<gg>tmp(n,0);
    vector<gg>reord(N+1,0);
    vector<gg>ord(N+1,0);
    sort(a,tmp,reord,ord,0,n-1,N);

    gg m;
    cin>>m;
    while(m--)
    {
        gg q;
        cin>>q;
        gg res=0;
        //第q层~1层交换reord~ord;
        for(gg i=q;i>=1;i--)
            swap(ord[i],reord[i]);
        for(gg i=1;i<=N;i++)
            res+=reord[i];       
        cout<<res<<'\n';     
    }
    return 0;
}
// 64 位输出请用 printf("%lld")


编辑于 2023-06-28 00:23:22 回复(0)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN=(1<<20)+5;
ll n,nn,m,a[MAXN],b[MAXN],f[25],z[25],c[MAXN];
void msort(ll a[],ll l,ll r,ll d,ll g[])
{
    if(l>=r)
        return ;
    int mid=l+r>>1;
    msort(a,l,mid,d-1,g);
    msort(a,mid+1,r,d-1,g);
    ll i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(a[i]<a[j])
            b[k++]=a[i++];
        else if(a[i]==a[j])
            b[k++]=a[i++];
        else
            b[k++]=a[j++],g[d]+=mid-i+1;
    }
    while(i<=mid)
        b[k++]=a[i++];
    while(j<=r)
        b[k++]=a[j++];
    for(i=l;i<=r;i++)
        a[i]=b[i];
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,q,x;
    cin>>n;
    nn=1<<n;
    for(i=1;i<=nn;i++)
        cin>>a[i],c[i]=a[i];
    msort(a,1,nn,n,f);
    reverse(c+1,c+nn+1);
    msort(c,1,nn,n,z);
    cin>>q;
    while(q--)
    {
        cin>>x;
        ll sum=0;
        for(i=x;i>=1;i--)
            swap(f[i],z[i]);
        for(i=1;i<=n;i++)
            sum=sum+f[i];
        cout<<sum<<endl;
    }
    return 0;
}

发表于 2022-04-21 22:30:56 回复(0)
import java.util.Scanner;
//主要是逆序对这块用的归并最后几个过不了
public class Main {
    static int[] nums = null;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        nums = new int[(int) Math.pow(2,n)];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = scanner.nextInt();
        }
        int m = scanner.nextInt();
        int[] count = new int[m];
        for (int i = 0; i < count.length; i++) {
            count[i] = scanner.nextInt();
        }
        for (int j : count) {
            System.out.println(getnums((int) Math.pow(2, j)));
        }
    }

    private static int getnums(int pow) {
        int l = 0,r = l+pow-1;
        while (l<r){
            int flag = r;
            while (l<flag){
                int a = nums[l];
                nums[l] = nums[flag];
                nums[flag] = a;
                l++;flag--;
            }
            l = r+1;
            r = l+pow-1>=nums.length?nums.length-1:l+pow-1;
        }

        return reversePairs(nums);
    }
    public static int reversePairs(int[] nums) {
        int len = nums.length;

        if (len < 2) {
            return 0;
        }

        int[] copy = new int[len];
        for (int i = 0; i < len; i++) {
            copy[i] = nums[i];
        }

        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    private static int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        if (nums[mid] <= nums[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int crossPairs = mergeAndCount(nums, left, mid, right, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    private static int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int count = 0;
        for (int k = left; k <= right; k++) {

            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;
                count += (mid - i + 1);
            }
        }
        return count;
    }

}

发表于 2022-02-10 19:41:01 回复(0)
WA ,不懂为啥,简单的cdq分治求逆序对。
有巨巨的请告诉我,谢谢。
#include "bits/stdc++.h"
using namespace std;

using i64 = long long;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n; cin >> n;
  int N = 1 << n;
  vector<i64> order(n + 1), reorder(n + 1);
  vector<int> a(N), b(N), temp(N);
  for(int i = 0;i < N; i++) {
    int x; cin >> x;
    a[i] = b[N - i - 1] = x;
  }
  function<void(int, int, int)> dfs1 = [&](int l, int r, int stp) {
    if(l == r) return ;
    int m = (l + r) / 2;
    dfs1(l, m, stp - 1);
    dfs1(m + 1, r, stp - 1);
    int p = l, q = m + 1;
    for(int i = l;i <= r; i++) {
      if((p <= m && a[p] <= a[q]) || q > r) temp[i] = a[p++];
      else order[stp] += p - l, temp[i] = a[q++];
    }
    for(int i = l;i <= r; i++) a[i] = temp[i];
  };
  function<void(int, int, int)> dfs2 = [&](int l, int r, int stp) {
    if(l == r) return ;
    int m = (l + r) / 2;
    dfs2(l, m, stp - 1);
    dfs2(m + 1, r, stp - 1);
    int p = l, q = m + 1;
    for(int i = l;i <= r; i++) {
      if((p <= m && b[p] <= b[q]) || q > r) temp[i] = b[p++];
      else reorder[stp] += p - l, temp[i] = b[q++];
    }
    for(int i = l;i <= r; i++) b[i] = temp[i];
  };
  dfs1(0, N - 1, n);
  dfs2(0, N - 1, n);
  int q; cin >> q;
  while(q--) {
    int x; cin >> x;
    for(int j = 1;j <= x; j++) swap(order[j], reorder[j]);
    i64 ans = 0;
    cout << accumulate(reorder.begin(), reorder.end(), 0) << '\n';
  }
}


发表于 2022-02-01 20:32:37 回复(0)
        这是一道挺有难度的问题,我 debug 了挺长时间终于通过了,写个题解分享一下思路吧;
        首先,利用归并排序求一个序列中的逆序对数,应该是一个比较经典的问题,这道题需要在这个基础之上做更多的工作。
        我们观察逆序对的一些性质,以题目所给的 [1, 3, 4, 2] 为例,有两个逆序对 [3, 2] 和 [4, 2],而如果我们按照 2 个数一组翻转之后,得到序列为 [3, 1, 2, 4], 这时候,逆序对为 [3, 1], [3, 2]。可以看到,[3, 2] 这个逆序对在翻转前后,是一直存在的,而  [4, 2] 这个原来存在的逆序对翻转之后则不再是逆序对了,同样的原来序列中的 [1, 3] 在翻转之后变成了新的逆序对 [3, 1]。通过上面的分析, 我们可以看到,在按照一定的组距翻转前后,原来是同一个组内的逆序对将消失,原来是同一个组内的顺序对将变成逆序对,原来跨越组间的逆序对将保持不变,还可以想到,原来想等的数对,无论是组间还是组内,都不会发生改变。
        根据上面的分析过程,我基于归并排序做了一些改编。在归并排序的过程中,记录下不同层次的归并中找到的逆序对数,相等的序列对数;简单说,用一个reverses数组做记录,reverses[i] 表示在对 2 的 i 次方个数之间做归并操作的时候(也就是对 2 的 i + 1 次方个数最最后一步)存在的逆序对数;用一个 equal 数组最记录,equal[i] 表示在对 2 的 i 次方个数之间做归并操作的时候(也就是对 2 的 i + 1 次方个数最最后一步)存在的相等的数组数目;
        于是很容易可以想到,所有的逆序对数为 reverses 数组的和;
        当按照某一组距进行翻转的时候,所有小于这个组距的下标对应的 reverses 数组中的值都会变化,也就是原来的逆序对变成顺序对,原来的顺序对变成逆序对;于是我们还应该先计算出所有的数对数目,我的代码中 num_pairs 数组就是这个含义,然后减去 equal 数组中记录的相等的数对,再减去翻转前 reverses 数组中记录的值。完整代码如下:
// 使用归并排序的思想
// 记录下组内的逆序对和组间的逆序对
#include<iostream>
#include<vector>
 
using namespace std;
 
void merge_sort(vector<int> &vec, vector<int> &trans, vector<long long> &reverses, vector<long long> &equal, int start, int end, int degree) {
    if(end - start == 1) {
        return;
    }
    int mid = start + (end - start) / 2;
    merge_sort(vec, trans, reverses, equal, start, mid, degree - 1);
    merge_sort(vec, trans, reverses, equal, mid, end, degree - 1);
    int l = start, r = mid, ptr = start;
    while(l < mid && r < end) {
        // 左边比右边大
        if(vec[l] > vec[r]) {
            reverses[degree] += (long long)(end - r);
            trans[ptr++] = vec[l++];
        } else if(vec[l] == vec[r]){
            int num1 = 0, num2 = 0, tmp = l, t = vec[l];
            while(tmp < mid && vec[tmp] == t) {
                num1++;
                tmp++;
            }
            while(r < end && vec[r] == t) {
                num2++;
                trans[ptr++] = vec[r++];
            }
            equal[degree] += (long long)num1 * (long long)num2;
        } else{
            trans[ptr++] = vec[r++];
        }
    }
    while(l < mid)
        trans[ptr++] = vec[l++];
    while(r < end)
        trans[ptr++] = vec[r++];
    for(int i = start; i < end; ++i)
        vec[i] = trans[i];
}
 
int main() {
    int n, m, size, ops;
    long long num, res = 0;
    cin >> n;
    size = 1 << n;
    vector<int> vec(size, 0);
    vector<int> trans(size, 0);
    vector<long long> reverses(n, 0);
    vector<long long> equal(n, 0);
    vector<long long> num_pairs(n, 0);
    for(int i = 0; i < n; ++i) {
        num = 1 << i;
        num_pairs[i] = num * num * (1 << (n - i - 1));
    }
    for(int i = 0; i < size; ++i)
        cin >> vec[i];
    merge_sort(vec, trans, reverses, equal, 0, size, n - 1);
    cin >> m;
    for(int i = 0; i < m; ++i) {
        cin >> ops;
        res = 0;
        for(int j = ops - 1; j >= 0; --j) {
            reverses[j] = num_pairs[j] - reverses[j] - equal[j];
        }
        for(int j = 0; j < n; ++j)
            res += reverses[j];
        cout << res << endl;
    }
    return 0;
}


发表于 2021-09-07 15:09:36 回复(0)
#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
using namespace std;


vector<long long> OrderCnt(21, 0);
vector<long long> reOrderCnt(21, 0);
void MergeSort(vector<long long>& vec, long long begin, long long end, int d) {
	assert((end - begin) == (long long)pow(2, d));
	if (begin == end || begin == end - 1)
		return;

	long long mid = (begin + end) / 2;
	MergeSort(vec, begin, mid, d - 1);
	MergeSort(vec, mid, end, d - 1);

	vector<long long> nums(end - begin);
	long long i = begin;
	long long j = mid;
	long long k = 0;
	while (i < mid && j < end) {
		if (vec[i] < vec[j]) {
			OrderCnt[d] += (end - j);
			nums[k++] = vec[i++];
		}
		else if (vec[i] > vec[j]) {
			reOrderCnt[d] += (mid - i);
			nums[k++] = vec[j++];
		}
		else if (vec[i] == vec[j]) {
			long long tmp = j + 1;
			while (tmp < end && vec[tmp] == vec[j])
				tmp++;
			OrderCnt[d] += (end - tmp);
			nums[k++] = vec[i++];
		}

	}

	while (i < mid)
		nums[k++] = vec[i++];
	while (j < end)
		nums[k++] = vec[j++];

	k = 0;
	for (int i = begin; i < end; i++)
		vec[i] = nums[k++];

	return;
}

int main() {
	int n;
	cin >> n;
	int len = pow(2, n);
	vector<long long> vec(len);
	for (long long i = 0; i < len; i++)
		cin >> vec[i];

	MergeSort(vec, 0, len, n);

	long long m, q;
	cin >> m;
	while (m--) {
		cin >> q;
		for (int i = 0; i <= q; i++)
			swap(OrderCnt[i], reOrderCnt[i]);

		long long cnt = 0;
		for (int i = 0; i <= n; i++)
			cnt += reOrderCnt[i];
		cout << cnt << endl;
	}
	return 0;
}

发表于 2021-07-15 18:09:48 回复(0)
// 这题思想就是找到各个层级顺逆序对 然后在操作的时候交换一下顺逆序对 思路很简单 但是坑点很多


#include<iostream>
#include<string.h>

using namespace std;

//找到各个层级的顺逆序对 注意处理值一样的 既不算逆序对也不算顺序对!!!
void findReverse(long long* a, long long start, long long end, long long* reverse, long long* order, long long pos){
    if(start == end - 1 || start == end) return;
    long long mid = (start + end) / 2;
    findReverse(a, start, mid, reverse, order, pos + 1);
    findReverse(a, mid, end, reverse, order, pos + 1);
    long long cur = 0;
    long long cur_reverse = 0;
    long long cur_order = 0;
    long long left_point = start;
    long long right_point = mid;
    long long* b = new long long[end - start];
    while(left_point < mid && right_point < end){
        while(left_point < mid && right_point < end && a[left_point] <= a[right_point]) {
            b[cur++] = a[left_point++];
            reverse[pos] += cur_reverse;
            
        }
        while(left_point < mid && right_point < end && a[left_point] > a[right_point]){
            b[cur++] = a[right_point++];
            cur_reverse ++;
        }
    }
    if(left_point < mid){
        reverse[pos] += cur_reverse * (mid - left_point);
    }

    // 计算该层级顺序对
    cur = 0;
    left_point = start;
    right_point = mid;
    while(left_point < mid && right_point < end){
        while(left_point < mid && right_point < end && a[left_point] < a[right_point]) {
            b[cur++] = a[left_point++];
            cur_order++;
        }
        while(left_point < mid && right_point < end && a[left_point] >= a[right_point]){
            b[cur++] = a[right_point++];
            order[pos] += cur_order;
        }
    }
    if(right_point < end){
        order[pos] += cur_order * (end - right_point);
    }


    // 合并
    while(left_point < mid){
        b[cur++] = a[left_point++];
    }
    while(right_point < end){
        b[cur++] = a[right_point++];
    }
    for(long long i = start; i < end; i++){
        a[i] = b[i - start];
    }
    delete[] b;
}


int main(){
    int n, m;
    cin >> n;
    long long* a = new long long[1<<n];
    // 数值范围较大  注意使用long long
    long long* reverse = new long long[(n+1)];
    long long* order = new long long[(n+1)];
    memset(a, 0, sizeof(long long)*(1<<n));
    memset(reverse, 0, sizeof(long long)*(n+1));
    memset(order, 0, sizeof(long long)*(n + 1));
    for(long long i = 0; i < (1<<n); i++){
        cin >> a[i];
    }
    findReverse(a, 0, 1<<n, reverse, order, 0);
    long long total = 0;
    for(long long i  = 0; i < n; i++){
        total += reverse[i];
    }
    cin >> m;
    long long q;
    while(m--){
        cin >> q;
        // 交换各层逆序对
        for(long long j = 1; j <= q; j++){
            total -= reverse[n - j];
            long long temp = reverse[n - j];
            reverse[n - j] =  order[n -j];
            order[n -j]= temp;
            total += reverse[n - j];
        }
        cout << total << endl;
    }
    delete[] a;
    delete[] reverse;
    delete[] order;
    return 0;
}
编辑于 2021-04-16 11:23:15 回复(0)
//开始忽略了还有相等情况,直接用对数总和减去逆序对了。实际上考虑相等情况,应该是顺序与逆序交替。
#include <iostream>
#include <vector>
#include <numeric>
 
using namespace std;
//void mergesort(vector<int> &nums,int left,int right,vector<int> &dp,int n);
//dp[i]表示长度为2^i长度左右两侧的归并数目.归并排序。
void mergesort(vector<long long> &nums,int left,int right,vector<long long> &dp,int k) {//归并排序,计算逆序对数量
    if(left>=right) return;
 
    int mid=(right+left)/2;
    mergesort(nums,left,mid,dp,k-1);
    mergesort(nums,mid+1,right,dp,k-1);
    int l=left,r=mid+1;
    while(l<=mid){
        while(r<=right&&nums[l]>nums[r]){
            ++r;
        }
        dp[k]+=r-mid-1;
        ++l;
    }
    vector<long long> temp(right-left+1);
    l=left,r=mid+1;
    int p=0;
    while(l<=mid||r<=right){
        if(l>mid){
            temp[p++]=nums[r++];
        }
        else if(r>right){
            temp[p++]=nums[l++];
        }
        else{
            if(nums[l]<nums[r]){
                temp[p++]=nums[l++];
            }
            else{
                temp[p++]=nums[r++];
            }
        }
    }
    for(int i=0;i<temp.size();++i){
        nums[left+i]=temp[i];
    }  
     
}
int main(){
    int n;
    cin>>n;
    int len=1<<n;
    vector<long long> v(len);
    for(int i=0;i<len;++i){
        cin>>v[i];
    }
    vector<long long> dp(n+1,0);
    vector<long long> rdp(n+1,0);
    vector<long long> rv(v.rbegin(),v.rend());
    mergesort(v,0,len-1,dp,n);    //计算逆序对。dp[n]表示间隔至少为2^(n-1)的逆序对。对应归并排序每次递归后子序列长度。
    mergesort(rv,0,len-1,rdp,n);   //计算顺序对,翻转数组则求逆序等于求原数组顺序
//    for(int i=0;i<=n;++i){
//        cout<<dp[i];
 //   }
//cout<<endl;
    int m;
    cin>>m;
    int q;
    for(int i=0;i<m;++i){
        cin>>q;
        long long res=0;
        for(int i=1;i<=n;++i){
            if(i<=q) swap(dp[i],rdp[i]);
            res+=dp[i];
//        cout<<endl;
        }
        cout<<res<<endl;
    }
     
     
     
    return 0;
}

发表于 2021-03-22 14:34:39 回复(0)
<p>1</p>
发表于 2020-11-26 15:29:10 回复(0)
有没有用MATLAB的大神,解读一下,就过了40,里面是不是有奇数个的啊,看题目应该都是偶数的。
clear
try
n = input('');
s = input('','s');
m = input('');
k = input('','s');

s = str2num(s);
k = str2num(k);
ss = zeros(m+1,2^n);
ss(1,:) = s;
for i1 = 1 : m
    q = zeros(2^(k(i1)),2^n/2^(k(i1)));
    q(:) = ss(i1,:);
    q = q';
    q = q(:,end:-1:1);
    q = q';
    ss(i1+1,:) = q(:);
end
y = zeros(m+1,1);
for i2 = 1 : 2^n-1
    y = y + sum(ss(:,i2+1:end)<ss(:,i2),2);
end
fprintf('%d\n',y(2:end));

catch
end

发表于 2020-08-21 17:02:29 回复(0)