BZOJ4240: 有趣的家庭菜园

题解:

首先预处理出$l_i$表示第$i$个数左侧比第$i$个数大的个数,$r_i$右侧同理.

首先脑补出我们应该将序列排成先单调不降,后单调不增的形式.

我们从大到小将数插入序列,考虑插入某个数,比这个数大的已经全部插入完毕了,由于排成那种形式,我们只能将这个数放在当前序列的头或尾.

若放在开头,则带来$l_i$的逆序对;否则带来$r_i$的逆序对.

显然每个数之间都是独立的,我们直接贪心就行了.

时间复杂度$O(nlogn)$.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;

#define N 300010
int n,_n,a[N],b[N];

inline int getc(){
	static const int L=1<<15;
	static char buf[L],*S=buf,*T=buf;
	if(S==T){
		T=(S=buf)+fread(buf,1,L,stdin);
		if(S==T)
			return EOF;
	}
	return*S++;
}
inline int getint(){
	int c;
	while(!isdigit(c=getc()));
	int x=c-'0';
	while(isdigit(c=getc()))
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}

int A[N],l[N],r[N];
inline int ask(int x){
	int re=0;
	for(;x;x-=x&-x)
		re+=A[x];
	return re;
}
inline void upd(int x){
	for(;x<=_n;x+=x&-x)
		++A[x];
}
int main(){
	n=getint();
	int i,j;
	for(i=1;i<=n;++i)
		a[i]=b[i]=getint();
	sort(b+1,b+n+1);
	_n=unique(b+1,b+n+1)-b-1;
	for(i=1;i<=n;++i)
		a[i]=lower_bound(b+1,b+_n+1,a[i])-b;
	for(i=1;i<=n;++i){
		l[i]=i-1-ask(a[i]);
		upd(a[i]);
	}
	memset(A,0,sizeof A);
	for(i=n;i>=1;--i){
		r[i]=n-i-ask(a[i]);
		upd(a[i]);
	}
	long long ans=0;
	for(i=1;i<=n;++i)
		ans+=min(l[i],r[i]);
	cout<<ans<<endl;
	return 0;
}