自动搬运

查看原文

来自洛谷，原作者为

	BigSmall_En time舟从此逝，code海寄余生

搬运于2025-08-24 22:31:42，当前版本为作者最后更新于2021-10-04 11:22:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

这题的题面太难读懂了，但是读懂了以后就会发现很简单。

题意理解

把 English 翻译成中文就是

给定一个需要排序的数组a[]
while(a不是一个排序好的序列){
	将a划分成多个连续的下降区间
	将所有这些区间(翻转)
}

要求统计翻转操作的次数。

例如：

1 2 6 5 4 3 8 7

划分完以后就是 1 2|6 5 4 3|8 7

每个"|"之间的区间就是下降的，一共有 $3$ 个区间

然后用 $3$ 次翻转操作就变成了 1 2 3 4 5 6 7 8

分析

为什么这样一直进行下去是可以完成排序的？

对于 8 7 6 5 1 2 3 4 ，变成 5 6 7 8 1 2 3 4 ，那么在区间 $[1,4]$ 和区间 $[5,8]$ 就是有序的了，同样可以想到对整个序列这样转之后序列就在一些范围上有序了。

由于题目要求划分后的序列长度必须为偶数，所以在有序区间 $[1,4]$ 内的数就不能划分，否则会划分成 5|6|7|8 、长度不为偶数

这样就会得到这样一个划分 5 6 7|8 1|2 3 4，恰好在两个有序区间的交界处且这个新的划分区间长度为 $2$

即使是翻转以后 5 6 7 1 8 2 3 4，也由于区间内元素的有序性只能划分为长度为2的新区间 5 6|7 1|8 2|3 4。

继续翻转之后也是这样的 5 6 1 7 2 8 3 4，也只能划分为长度为2的新区间。

这样就等价于只能选择相邻的元素交换了。也就等价去经典的求逆序对问题了。

题解

根据以上的分析可以得到这样的思路：先按照题意分组翻转一次。然后用树状数组或归并排序求逆序对就可以了。

代码：

#include<cstdio>
using namespace std;
const int N=100005;
int n,a[N],c[N];long long ans;
void swap(int& x,int& y){x^=y;y^=x;x^=y;}//交换两个元素
void reverse(int l,int r){//翻转区间[l,r]内的元素
	for(int i=l;i<=r&&(i<<1)<l+r;++i)swap(a[i],a[r+l-i]);
	++ans;//顺便统计答案
}
int lowbit(int x){return x&-x;}//下面三行是经典的树状数组
void update(int i,int v){for(;i<=n;i+=lowbit(i))c[i]+=v;}
int getsum(int i){int ans=0;for(;i;i-=lowbit(i))ans+=c[i];return ans;}
int main(){
	scanf("%d",&n);
	int las=1;scanf("%d",&a[1]);//先将序列按要求翻转一次
	for(int i=2;i<=n;++i){
		scanf("%d",&a[i]);
		if(a[i]>a[i-1]){
			reverse(las,i-1);
			las=i;
		}
	}reverse(las,n);
	for(int i=n;i>=1;--i){//然后直接树状数组求逆序对正确性就可以保证了
		ans+=getsum(a[i]);
		update(a[i],1);
	}printf("%lld\n",ans);
	return 0;
}//	 94ms /  1.37MB /  705B C++98