今天这场hdu多校打的有些心力憔悴，有些难受，感觉有力没出使，还有就是感觉自己还是懂的少，有些东西想不到，也找不到规律，这就很难受了，那道线段树的题，总感觉能出能出，但最后也不出来，还有那个构造题和方块黑白种类的那个题，也是感觉能做，推推推，就会也没弄对，感觉还是脑洞不够大，看的题也太少了。这个假期一定要多多见题。。。。
Swaps and Inversions
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<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int c[MAXN];
int lowbit(int x)
{
return x&(-x);
}
int sum(int x)
{
int res=0;
while(x>0)
{
res+=c[x];
x -=lowbit(x);
}
return res;
}
void add(int x,int v)
{
while(x<=MAXN)
{
c[x]+=v;
x+=lowbit(x);
}
}
struct node
{
int v;
int index;
bool operator <(const node& b)const
{
return v<b.v;
}
}nodes[MAXN];
int b[MAXN];//将初始数组重新赋值后 相对大小不变的新数组
int main()
{
int n,x,y;
while(~scanf("%d%d%d",&n,&x,&y))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&nodes[i].v);
nodes[i].index=i;
}
sort(nodes+1,nodes+n+1);
memset(b,0,sizeof(b));
b[ nodes[1].index ]=1;
for(int i=2;i<=n;i++)
{
if(nodes[i].v==nodes[i-1].v)
b[ nodes[i].index ]=b[ nodes[i-1].index ];
else
b[ nodes[i].index ]=i;
}
memset(c,0,sizeof(c));
long long ans=0;
for(int i=1;i<=n;i++)
{
add(b[i],1);//当前扫描的值是b[i],那么在x[b[i]]这个点上加1,表示又出现了1个b[i]值
ans += sum(n)-sum(b[i]);
}
int lala=min(x,y);
printf("%I64d\n",ans*lala);
}
}