다음과 같은 관찰만 할 수 있다면 아이디어는 간단합니다.
A<B를 만족하는 네 정수 A, B, C, D와 A, B를 잇는 선분 X와 C, D를 잇는 선분 Y에 대해 다음과 같은 명제가 성립합니다.
Lemma 1. X와 Y가 교차함은 A<C<B<D와 동치이다.
이 두 명제는, 몇가지 케이스를 나눠 살펴봄으로써 관찰할 수 있습니다.
Lemma 1에 의해 같은 소가 지나는 점을 잇는 선분을 번호가 작은 점을 기준으로 정렬한다면, 어떤 선분 K에 대해 K와 교차하며 K보다 앞에 위치하는 선분의 번호가 큰 점의 번호는 K의 번호가 큰 점의 번호보다 작아야 합니다.
이를 세그먼트 트리로 처리해준다면, $O(nlogn)$ 정도에 답을 구할 수 있습니다.
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
int arr[100010];
int f[50010];
int s[50010];
vector<pii> v;
const int nmax=100010;
int seg[nmax<<2];
void upd(int idx,int l,int r,int p,int v){
if(l>p||r<p)return;
if(l==r){
seg[idx]=v;
return;
}
int m=l+r>>1,le=idx<<1,ri=le|1;
upd(le,l,m,p,v);upd(ri,m+1,r,p,v);
seg[idx]=seg[le]+seg[ri];
}
int query(int idx,int l,int r,int s,int e){
if(l>e||r<s)return 0;
if(s<=l&&r<=e)return seg[idx];
int m=l+r>>1,le=idx<<1,ri=le|1;
return query(le,l,m,s,e)+query(ri,m+1,r,s,e);
}
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=2*n;i++){
cin>>arr[i];
if(f[arr[i]]){
s[arr[i]]=i;
v.emplace_back(f[arr[i]],s[arr[i]]);
}
else{
f[arr[i]]=i;
}
}
sort(v.begin(),v.end());
int res=0;
for(int i=0;i<v.size();i++){
res+=query(1,1,2*n,v[i].fi,v[i].se);
upd(1,1,2*n,v[i].se,1);
}
cout<<res;
}