树状数组 POJ2299&HDU6318 逆序对 离散化树状数组&归并排序

逆序对

i<j时，a[i]>a[j]，则（a[i],a[j]）为逆序对。

求解方法有两种：

1）离散化树状数组

      很多时候a[i]>>n，这时候就需要离散化，给序列编号。

      具体理解：i为序列1~n，a[i]为初始序列，编号index[i]则为a[i]应该处于的位置；sum求得index[i]前及其自身出现过的数字，i-sum()为小于index[i]但未出现即位置出现在其后的即逆序。

2）归并排序

      递归去实现：

      1.分 左 右

      2.合 左 右

 

POJ2299

Ultra-QuickSort

Time Limit: 7000MS		Memory Limit: 65536K
Total Submissions: 70687		Accepted: 26544

Description

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.

Input

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.

Output

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.

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

 

逆序对典型题目，这里用归并实现：

#include <cstdio>
#include <cstring>

const int maxn=500020;

int n;
long a[maxn],b[maxn];
long long ans;

//归并
long long Merge(int l,int mid,int r)
{
	long long sum=0;
	int left_index=l,right_index=mid+1;
	int re_index=l;
	while(left_index<=mid&&right_index<=r){
		if(a[left_index]>a[right_index]){
			b[re_index++]=a[right_index++];
			sum+=mid+1-left_index;//(right_index-re_index);	//a[left_index]>a[right_index],right_index左边有(right_index-re_index)个数比他大//也是mid-left——index+1
		}
		else{
			b[re_index++]=a[left_index++];
		}
	}
	while(left_index<=mid){
		b[re_index++]=a[left_index++];
		//if(left_index<mid+1) ++sum;	//这样写是错的想简单了，有很多时候不只是+1就能解决的
	}
	while(right_index<=r){
		b[re_index++]=a[right_index++];
	}
	return sum;
}

//分治
long long MergeSort(int l,int r)
{
	if(l==r)	//只剩一位时不需要再排
		return 0;
	long long sum=0;
	int mid=(l+r)/2;
	sum+=MergeSort(l,mid);
	sum+=MergeSort(mid+1,r);
	sum+=Merge(l,mid,r);
	for(int i=l;i<=r;++i)
		a[i]=b[i];
	return sum;
}

int main()
{
	while(scanf("%d",&n)){
		if(!n) break;
		for(int i=1;i<=n;++i){
			scanf("%ld",&a[i]);
		}
		printf("%lld\n",MergeSort(1,n));
	}

	return 0;
}

 

HDU6318

Swaps and Inversions

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2326    Accepted Submission(s): 884
 

Problem Description

Long long ago, there was an integer sequence a.
Tonyfang think this sequence is messy, so he will count the number of inversions in this sequence. Because he is angry, you will have to pay x yuan for every inversion in the sequence.
You don't want to pay too much, so you can try to play some tricks before he sees this sequence. You can pay y yuan to swap any two adjacent elements.
What is the minimum amount of money you need to spend?
The definition of inversion in this problem is pair (i,j) which 1≤i<j≤n and ai>aj.

 

Input

There are multiple test cases, please read till the end of input file.
For each test, in the first line, three integers, n,x,y, n represents the length of the sequence.
In the second line, n integers separated by spaces, representing the orginal sequence a.
1≤n,x,y≤100000, numbers in the sequence are in [−109,109]. There're 10 test cases.

 

Output

For every test case, a single integer representing minimum money to pay.

 

Sample Input

3 233 666

1 2 3

3 1 666

3 2 1

 

Sample Output

0

3

 

离散化树状数组实现。注意考虑相等的情况。注意操作顺序的安排。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lowbit(x) x&(-x)
using namespace std;

const int maxn=100020;
const int inf=0x3f3f3f3f;

int n,x,y;
int c[maxn],p[maxn];
long long ans;

struct node{
	long m;
	int num;
}a[maxn];

bool cmp(node n1,node n2)
{
	return n1.m<n2.m;
}

int sum(int x)
{
	int sum=0;
	for(;x;x-=lowbit(x)){
		sum+=c[x];
	}
	return sum;
}

void add(int x,int y)
{
	for(;x<=n;x+=lowbit(x)){
		c[x]+=y;
	}
}

int main()
{
	while(~scanf("%d%d%d",&n,&x,&y)){
		ans=0;
		memset(c,0,sizeof(c));
		for(int i=1;i<=n;++i){
			scanf("%ld",&a[i].m);
			a[i].num=i;
		}
		sort(a+1,a+n+1,cmp);
		int k=1;
		p[a[1].num]=k;
		for(int i=2;i<=n;++i){	//离散化
			if(a[i].m==a[i-1].m) p[a[i].num]=k;		//考虑相等的情况
			else p[a[i].num]=++k;
		}
		for(int i=1;i<=n;++i){
			add(p[i],1);	//操作顺序很妙，这样子能够减掉本位，也考虑了减掉所有相等的
			ans+=(i-sum(p[i]));
		}
		printf("%lld\n",ans*min(x,y));
	}

	return 0;
}