# 題目

zerojudge f315. 4. 低地距離

# 解題思路

目前沒東西...

# 程式碼

#include<bits/stdc++.h>
using namespace std;
#define N 100005
typedef long long LL;
pair<int,bool> a[N<<1];
bool c[N];
LL inv(int l,int r){
    if(l+1==r)
        return 0;
    int m=(l+r)>>1;
    LL ans=inv(l,m)+inv(m,r);
    pair<int,bool> temp[r-l];
    int j=m,p=0;
    for(int i=l;i<m;i++){
        while(j<r && a[j]<a[i])
            temp[p++]=a[j++];
        temp[p++]=a[i];
        if(a[i].second) ans-=(j-m);
        else ans+=(j-m);
    }
    for(int i=0;i<p;i++)
        a[l+i]=temp[i];
    return ans;
}
int main(){
    int n;
    cin>>n;
    n<<=1;
    for(int i=0;i<n;i++){
        cin>>a[i].first;
        if(c[a[i].first])
            a[i].second=1;
        else
            c[a[i].first]=1;
    }
    cout<<inv(0,n);
}
更新於 閱讀次數 次