题目大意

给定若干个未排序的序列，利用冒泡排序原理(交换两个相邻序列元素)，求将它们各自变成升序的最小操作数，对于每一个序列输出一个答案。

思路:

其实还是求逆序对个数,但数的范围比较大( $1 \leq x \leq 9999999999$ ),而个数只有$5 \times 10^5$,此时便需要离散化。

离散化

STL

const int maxn=6e5+10;
int a[maxn],b[maxn],n,size;
for(int i=1; i<=n; i++)
{
		scanf("%d",&a[i]);
		b[i]=a[i];
}
sort(a+1,a+n+1);
size=unique(a+1,a+n+1)-a-1;
for(int i=1; i<=n; i++)
{
	b[i]=upper_bound(a+1,a+n+1,b[i])-a-1;
	//size=max(b[i],size);
}

手%

const int maxn=6e5+10;
int a[maxn],b[maxn],f[maxn],fu[maxn],n,ma=0;
for(int i=1; i<=n; i++)
{
	scanf("%d",&a[i]);
	b[i]=a[i];
}
sort(a+1,a+n+1);
int cnt=0;
fu[++cnt]=a[1];
for(int i=2; i<=n; i++) if(a[i]!=a[i-1]) fu[++cnt]=a[i];
ma=0;
for(int i=1; i<=n; i++)
{
	f[i]=bs(b[i],1,cnt);
	ma=max(ma,f[i]);
}
int bs(int val,int l,int r)
{
	int m;
	while(l<r)
	{
		m=(l+r)>>1;
		if(fu[m]>=val) r=m;// >= !! 
		else l=m+1;
	}
	return l;
}

Code(BIT):

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lowbit(x) ((x)&(-(x)))
#define cls(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=6e5+10;
typedef long long ll;
ll sum[maxn];
int a[maxn],b[maxn],n,size;
void update(int,int);
ll query(int);
ll getsum(int,int);
int main()
{
//	freopen("data1.in","r",stdin);
	while(~scanf("%d",&n)&&n)
	{
		cls(sum,0),cls(a,0),cls(b,0),size=0;
		for(int i=1; i<=n; i++)
		{
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		sort(a+1,a+n+1);
	//	size=unique(a+1,a+n+1)-a-1;
		for(int i=1; i<=n; i++)
		{
			b[i]=upper_bound(a+1,a+n+1,b[i])-a-1;
			size=max(b[i],size);
		}
		ll ans=0;
		cls(sum,0);
		for(int i=1; i<=n; i++)
		{
			ans+=getsum(b[i]+1,size);
			update(b[i],1);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
void update(int p,int val)
{
	for(int i=p; i<=size; i+=lowbit(i))
	{
		sum[i]+=val;
	}
}
ll query(int p)
{
	ll ret=0;
	for(int i=p; i>0; i-=lowbit(i))
	{
		ret+=sum[i];
	}
	return ret;
}
ll getsum(int l,int r)
{
	return query(r)-query(l-1);
}