CF351E Jeff and Permutation 做题记录

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

$1\le n\le 2000$，$|a_i|\le 10^5$。

考虑一对 $(i,j)$（$i<j$）对逆序对个数的贡献：

• $|a_i|>|a_j|$：有贡献当且仅当 $a_i$ 取 $|a_i|$；
• $|a_i|<|a_j|$：有贡献当且仅当 $a_j$ 取 $-|a_j|$；
• $|a_i|=|a_j|$：有贡献当且仅当 $a_i$ 取 $|a_i|$，$a_j$ 取 $-|a_j|$ 且 $a_i\not=0,a_j\not=0$；

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

• $a_x=|a_x|$ 时：$i<x$ 且 $|a_i|<|a_x|$ 的 $i$ 的个数；
• $a_x=-|a_x|$ 时：$i>x$ 且 $|a_i|<|a_x|$ 的 $i$ 的个数；

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

若存在 $|a_i|=|a_j|$ 的 $(i,j)$，这个贪心其实也是对的。因为对于所有 $|a_i|=w$，在原序列中一定存在一个分界点 $k$，满足 $i\le k$ 的 $a_i$ 是负数，$i>k$ 的 $a_i$ 是正数。因为 $a_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;
}