2018 Multi-University Training Contest 2 ：Swaps and Inversions

#include<cstdio>
#include<cstring>
using namespace std;

typedef long long ll;
const int maxn=100000+100;

int ans[maxn];
int tmp[maxn];
ll cnt;

inline void Union(int l,int r,int mid){
    
    int tmp1_l=l;
    int tmp2_l=mid+1;
    int start=l;
    while(tmp1_l<=mid && tmp2_l<=r){
        
        if(ans[tmp1_l]<=ans[tmp2_l]){
            
            tmp[start++]=ans[tmp1_l++];
        }
        else{
            
            tmp[start++]=ans[tmp2_l++];
            cnt+=(ll)(mid-tmp1_l+1);
        }
    }
    while(tmp1_l<=mid) tmp[start++]=ans[tmp1_l++];
    while(tmp2_l<=r)   tmp[start++]=ans[tmp2_l++];
    for(int i=l;i<=r;i++) ans[i]=tmp[i];
}

inline void kaven(int l,int r){
    
    if(l>=r) return ;
    int mid=(l+r)>>1;
    kaven(l,mid);
    kaven(mid+1,r);
    Union(l,r,mid);
}

int main(){
    
    int n,x,y;
    while(scanf("%d%d%d",&n,&x,&y)==3){
        
        cnt=0;
        for(int i=1;i<=n;i++) scanf("%d",&ans[i]);
        kaven(1,n);
        ll money=x<y?x:y;
        printf("%lld\n",cnt*money);
    }
}