CF351E Jeff and Permutation 做题记录

给出数组 aa ,你可以改变每个数的正负,求逆序对数最少是多少。

1n20001\le n\le 2000ai105|a_i|\le 10^5

考虑一对 (i,j)(i,j)i<ji<j)对逆序对个数的贡献:

  • ai>aj|a_i|>|a_j|:有贡献当且仅当 aia_iai|a_i|
  • ai<aj|a_i|<|a_j|:有贡献当且仅当 aja_jaj-|a_j|
  • ai=aj|a_i|=|a_j|:有贡献当且仅当 aia_iai|a_i|aja_jaj-|a_j|ai=0,aj=0a_i\not=0,a_j\not=0

暂时先不考虑第三种情况,不难发现 (i,j)(i,j) 的贡献和 aia_iaja_j 中绝对值最大的那个的取值直接挂钩,那么 axa_x 对逆序对个数的贡献为:

  • ax=axa_x=|a_x| 时:i<xi<xai<ax|a_i|<|a_x|ii 的个数;
  • ax=axa_x=-|a_x| 时:i>xi>xai<ax|a_i|<|a_x|ii 的个数;

所以有一个显然的贪心:每个 xx 都从这两个值中取最小的累加进答案。容易发现如果不存在 ai=aj|a_i|=|a_j|(i,j)(i,j) 则这个贪心一定是正确的,因为每个 xx 的贡献是独立的。

若存在 ai=aj|a_i|=|a_j|(i,j)(i,j),这个贪心其实也是对的。因为对于所有 ai=w|a_i|=w,在原序列中一定存在一个分界点 kk,满足 iki\le kaia_i 是负数,i>ki>kaia_i 是正数。因为 axa_x 贡献的取值一定是单调的。

代码如下:

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=100005;

int n,a[S],id[S];
int tr[S];

inline void add(int pos,int val)
{
	for(int i=pos;i<=n;i+=i&-i) tr[i]+=val;
}

inline int que(int pos)
{
	int res=0;
	for(int i=pos;i>=1;i-=i&-i) res+=tr[i];
	return res;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]=abs(a[i]),id[i]=i;
	sort(id+1,id+n+1,[&](int x,int y){return a[x]<a[y];});
	long long ans=0;
	for(int i=1,j=0;i<=n;i++)
	{
		while(j<i&&a[id[j+1]]!=a[id[i]]) add(id[++j],1);
		ans+=min(que(id[i]),j-que(id[i]));
	}
	printf("%lld\n",ans);
	return 0;
}