Swaps and Inversions

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

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

题意：

给出了逆序对的定义，这个英文是真的有毒， 队友一直跟我争执我是不是看错题目了，害我也怀疑了一下自己。

给出一个数组的大小，数组内的每个数大小为-10的九次方到10的九次方，如果数组内出现一个逆序对你就要支付x元，你可以进行一个操作，交换相邻的两个数字，支付y元 ，请问最小花费多少？

思路：

不难发现，因为是交换相邻的两个数字，每次交换都是为了能减少逆序对，且只能减少一个，所以只要求出有多少个逆序对，答案再去乘以min（x，y），求逆序队的方法有两种， 一种是归并排序，一种是树状数组，比赛时敲了树状数组wa了几发，怀疑了人生，最后迫于无奈，写了归并排序，赛后才知道树状数组要离散化，不然数组数字太大过不了QAQ。

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define N 100010
int c[N];
int aaa[N], bbb[N];
int n;
int lowbit(int i) {
	return i&(-i);
}
int insert(int i,int x) {
	while(i<=n) {
		c[i]+=x;
		i+=lowbit(i);
	}
	return 0;
}

int getsum(int i) {
	int sum=0;
	while(i>0) {
		sum+=c[i];
		i-=lowbit(i);
	}
	return sum;
}
void discre() {//离散化 
	map<int,int>ma;
	sort(bbb + 1,bbb + 1 + n);
	int cnt = 1;
	for(int i = 1; i <= n; i++) {
		if(i == 1) {
			ma[bbb[i]] = cnt;
		} else {
			if(bbb[i] != bbb[i - 1]) {
				ma[bbb[i]] = ++cnt;
			} else {
				ma[bbb[i]] = cnt;
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		aaa[i] = ma[aaa[i]];
	}
}
int main() {
	int x, y;
	while(~scanf("%d%d%d",&n,&x,&y)) {
		ll ans=0;
		memset(c,0,sizeof(c));
		for(int i=1; i<=n; i++) {
			scanf("%d", &aaa[i]);
			bbb[i] = aaa[i];
		}
		discre();
		for(int i=1; i<=n; i++) {
			insert(aaa[i],1);
			ans += i-getsum(aaa[i]);
		}
		int z = min(x,y);
		ll k = z * ans;
		printf("%lld\n",k);
	}
	return 0;
}