codeforces414C. Mashmokh and Reverse Operation

题目

题意：给出一个长度为2^n的数列，然后要将其分成每段长度为2^q的小段，将每段进行反转，问新数列的逆序数。每次操作都是建立在上一次的操作之上。

题解：

太怒膜了这种题。思路神题

题解

首先，反转之后的逆序数，在反转之前是可以得到的（即把数列反过来看）。

然后，将数分解成2^q段，然后反转，其实相当于归并排序中的1-q层进行了反转（想想为什么，提示：归并排序是每次将数列分成两半），而反转后的逆序数在之前已经求到了，于是不需要进行归并排序，而只需要把所有归并排序的逆序数加起来就行了。

并且，归并排序还可以做简易的就可以了（每次都完完整整排序反而更加麻烦）。

--------------------- 本文来自 wunianqingdada 的CSDN 博客 ，全文地址请点击：https://blog.csdn.net/u013573306/article/details/23851033?utm_source=copy

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[2000001],m,q;
long long f[2000001][2],ans;
void gb(int x,int l,int r){
	int i;
	if(l>=r)return;
	int mid=(l+r)/2;
	gb(x-1,l,mid);gb(x-1,mid+1,r);
	for(i=l;i<=mid;i++){
		f[x][0]+=lower_bound(a+mid+1,a+r+1,a[i])-(a+mid+1);
		f[x][1]+=r-mid-(upper_bound(a+mid+1,a+r+1,a[i])-(a+mid+1));
	}
	sort(a+l,a+r+1);
}
int main(){
	int i;
	scanf("%d",&n);
	for(i=1;i<=(1<<n);i++)scanf("%d",&a[i]);
	gb(n,1,1<<n);
	scanf("%d",&m);
	while(m--){
		scanf("%d",&q);
		ans=0ll;
		for(i=1;i<=q;i++)swap(f[i][0],f[i][1]);
		for(i=1;i<=n;i++)ans+=f[i][0];
		printf("%lld\n",ans);
	}
}