題目連結
題意：有一個長度為n的亂序集合，如果一個子序列為逆序，你就要付x元，或者你可以選擇修改一個相鄰的數字，你就要付y元，問最少你要付多少錢。（其實你交換一個存在逆序的相鄰數字就可以減少一個逆序數）
這題不知道是題目的意思太繞還是怎樣，我看了很久硬是每看懂題目在講什麼，後來看了一下大佬們的代碼和解釋才知道，這不就是樹狀數組的入門題嗎。。我。。。英語和國文閱讀能力大概是沒救了。。。
思路：就是算這個集合存在多少逆序數，最後的答案乘min(x,y)就可以了。（好像應該也可以用線段樹做，不過這個就是數組數組的闆子題）
AC代碼：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int c[maxn],a[maxn],b[maxn];
int n, x, y;
ll lowbit(int x){
return x&(-x);
}
void add(int x,int y){
for(int i = x; i <= n; i+=lowbit(i))
c[i] += y;
}
ll query(int x){
ll ans = 0;
for(int i = x; i > 0; i-=lowbit(i))
ans += c[i];
return ans;
}
int main(){
int i;
while(scanf("%d%d%d",&n,&x,&y)!=EOF){
memset(c, 0, sizeof(c));
for(i = 1; i <= n; i++){
scanf("%d",&a[i]);
b[i] = a[i];
}
sort(b+1, b+1+n);
ll ans = 0;
for(i = n; i > 0; i--){ //這裡要從n開始，因為可能存在相同的數字，把數字按原本位置從後往前插入樹狀數組，檢視在它原本位置後面有多少個小于它的數，就存在多少逆序數
int t = lower_bound(b+1, b+1+n, a[i])-b; //找到第一個大于等于a[i]的數的位置，是以查詢的時候要減1
ans += query(t-1);
add(t, 1);
}
printf("%lld\n",ans*min(x,y));
}
return 0;
}