正文开始

阅读理解

有

n

个数，从前往后扫，将每一个最长单调下降连续子序列翻转，扫到头后再从头开始扫，求翻转次数。

思路

这道题卡了我挺久的，原因就出在这一句话上：“保证在第一次划分时每个 slope 的长度都为偶数” 这一句话很关键，但我当时没看到。

那么这么一句不起眼的话有什么用呢？稍微模拟一下我们可以发现，有了这个条件的限制，那么在第一次翻转后，剩下的所有单调下降的连续子序列的长度要么为

2

，要么为

1

，这也就说明每一次翻转都是在交换相邻的两个数，那么就转化为了经典的求冒泡排序的交换次数，就可以直接用树状数组或者归并排序求逆序对的个数了。

代码

由于本蒟蒻不会树状数组，于是用的线段树代替。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[1000005],ans;
int t[1000005];
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
inline void push_up(int p){t[p]=t[ls(p)]+t[rs(p)];}
inline void update(int id,int p,int pl,int pr){
	if(pl==pr&&pl==id){t[p]++;return ;}
	int mid=pl+pr>>1;
	if(id<=mid)update(id,ls(p),pl,mid);
	else update(id,rs(p),mid+1,pr);
	push_up(p);
}
inline int query(int L,int R,int p,int pl,int pr){
	if(L>R)return 0;
	if(L<=pl&&pr<=R)return t[p];
	int mid=pl+pr>>1,res=0;
	if(L<=mid)res+=query(L,R,ls(p),pl,mid);
	if(R>mid)res+=query(L,R,rs(p),mid+1,pr);
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	a[n+1]=INT_MAX;
	int cnt=1;
	for(int i=2;i<=n+1;i++){//先按照题意模拟一次 
		if(a[i]>=a[i-1]){
			if(cnt>1){
				for(int j=i-cnt,k=i-1;j<k;j++,k--)swap(a[j],a[k]);
				ans++;
			}
			cnt=1;
		}
		else cnt++;
	}
	update(a[n],1,1,n);//预处理最后一个数 
	for(int i=n-1;i;i--){
		ans+=query(1,a[i]-1,1,1,n);//查找在  i 之后有多少个小于 a[i] 的数，计入贡献 
		update(a[i],1,1,n);
	}
	cout<<ans;
	return 0;
}

题解：P7629 [COCI 2011/2012 #1] SORT

文章操作

正文开始

阅读理解

思路

代码

相关推荐

评论

题解：P7629 [COCI 2011/2012 #1] SORT