51nod P3121 小陶与杠铃片【树状数组】

51nod P3121 小陶与杠铃片【树状数组】 题目

思路

这道题其实是求逆序对个数
为什么呢？
因为只能选相邻两片杠铃，那么这就是一个逆序对不断减少的过程，逆序对数量为零那么就排好序了。
而求逆序对个数显然可以用树状数组解决

代码

#include
#include
#include
using namespace std;
long long n,c[200010],ans,a[200010];
void insert(long long x,long long y)
{
	while(x<=200001)
	 {
	 	c[x]+=y;
	 	x+=(x&-x);
	 }
}
long long query(long long x)
{
	long long js=0;
	while(x)
	 {
	 	js+=c[x];
	 	x-=(x&-x);
	 }
	return js;
}
int main()
{
	scanf("%lld",&n);
	for(long long i=1; i<=n; i++)
	   scanf("%lld",&a[i]);
    for(long long i=1; i<=n; i++)
     {
     	ans+=(query(200001)-query(a[i]));
     	insert(a[i],1);
	 }
	printf("%lld",ans);
	return 0;
}