2299:Ultra-QuickSort （ 树状数组 求逆序对 ）

题目来源：http://bailian.openjudge.cn/practice/2299?lang=en_US

Ultra-QuickSort

• 查看
• 提交
• 统计
• 提示
• 提问

总时间限制: 

7000ms

 

内存限制: 

65536kB

描述

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 

9 1 0 5 4 ,

Ultra-QuickSort produces the output 

0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

输入

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

输出

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

样例输入

5
9
1
0
5
4
3
1
2
3
0

样例输出

6
0

---

裸的一个树状数组题

关于树状数组 ： https://blog.csdn.net/qq_41431457/article/details/88945833

#include<bits/stdc++.h>
using namespace std;
using lom = long long;

const int M = 500005;
int a[M], b[M], t[M], n;

int lowbit(int x)
{
	return x & -x;
}

int add(int x)//把包含这个数的结点都更新 
{
	while(x <= n)//范围 
	{
		t[x]++;
		x += lowbit(x);
	}
}

int sum(int x)//查询1~X有几个数加进去了 
{
	int res = 0;
	while(x >= 1)
	{	
		res +=t [x];
		x -= lowbit(x);
	}
	return res;
}

bool cmp(int x, int y)
{
	if(a[x] == a[y]) return x > y;
	return a[x] > a[y];
}

int main()
{
	while(cin >> n && n)
	{
		memset(t, 0, sizeof t);
		lom ans = 0;
		
		for(int i = 1; i <= n; i++)
		{
			scanf("%d", a + i);
			b[i] = i;
		}
		
		sort(b + 1, b + n + 1, cmp);
		
		for(int i = 1; i <= n; i++)
		{
			add(b[i]);
			ans += sum(b[i] - 1);
		}
		
		cout << ans << endl;
	}
	
	return 0;
}

---

归并排序版：

#include<bits/stdc++.h>
#define M 500005
using namespace std;
int a[M],t[M],n;
long long ans=0;
void msort(int l,int r)
{
	if(l==r) return ;
	
	int mid=l+r>>1;
	msort(l,mid);	
	msort(mid+1,r);
	
	int i=l, j=mid+1, k=l;
	while(i<=mid&&j<=r)
		if(a[i]<=a[j]) t[k++]=a[i++];
		else t[k++]=a[j++], ans+=mid-i+1;
		
	while(i<=mid) t[k++]=a[i++];
	while(j<=r)   t[k++]=a[j++];
	
	for(int i=l;i<=r;i++) a[i]=t[i];
}
int main()
{
//	freopen("in.txt","r",stdin);
	while(cin>>n && n)
	{
		ans = 0;
		
		for(int i=1;i<=n;i++) cin>>a[i];
	
		msort(1,n);	
	
		cout << ans << endl;
	}
	
	return 0;
}