# 題目
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); | |
} |