P1774 最接近神的人_NOI导刊2010提高（02）

P1774 最接近神的人_NOI导刊2010提高（02）

---

关于此题为什么可以使用求逆序对的方法来做

假设一个数\(a_i\)，且前\(i-1\)个数已经成为单调增的数列。

我们要从前\(a_1\)至\(a_{i-1}\)个数的有序队列中插入\(a_i\)。

且只能使用类似冒泡排序的方法交换。

那么，插入这个数\(a_i\)需要交换的次数就是他的逆序对数。

有如下两种\(i\)的取值情况

逆序对数

\(0\)

可以推得

所以这种题就是求一个逆序对的个数，就\(\mathfrak{van}\)♂了

有道云markdown真难用

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

struct node

{

	long long val;

	int pos;

};

node data[600000];

bool compare(const node &a,const node &b)

{

	return a.val>b.val;

}

int bit[600000];

int num;

void insert(int pos,int val)

{

	while(pos<=num)

	{

		bit[pos]+=val;

		pos+=pos&(-pos);

	}

	return ;

}

long long  sum(int pos)

{

	long long res=0;

	while(pos)

	{

		res+=bit[pos];

		pos-=pos&(-pos);

	}

	return res;

}

int comp[600000];

int main()

{

	int n;

	scanf("%d",&n);

	num=n;

	for(int i=1;i<=n;i++)

	{

		scanf("%lld",&data[i].val);

		data[i].pos=i;

	}

	sort(data+1,data+1+n,compare);

	long long now=-(1ll<<61);

	int ha=0;

	for(int i=1;i<=n;i++)

	{

		if(data[i].val!=now)

		{

			now=data[i].val;

			ha+=1;

		}

		comp[data[i].pos]=ha;

	}

	long long ans=0;

	for(int i=1;i<=n;i++)

	{

		ans+=sum(comp[i]-1);

		insert(comp[i],1);

	}

	printf("%lld",ans);

}