소가 길을 건넌 이유 III

농부 존(Farmer John)의 농장 구조는 꽤 독특해서, 소들이 낮 동안 풀을 뜯는 중심 들판의 둘레를 커다란 원형 도로가 둘러싸고 있다. 매일 아침 소들은 들판으로 가는 길에 이 도로를 건너고, 매일 저녁 들판을 떠나 헛간으로 돌아갈 때 다시 도로를 건넌다.

알다시피 소는 습관의 동물이라, 매일 같은 방식으로 도로를 건넌다. 각 소는 들판에서 나오는 지점과 다른 지점으로 들판에 들어가며, 이 모든 건너는 지점들은 서로 다르다. 농부 존은 정수 ID \(1 \ldots N\)으로 편리하게 식별되는 \(N\)마리의 소를 기르고 있으므로, 도로 둘레에는 정확히 \(2N\)개의 건너는 지점이 있다. 농부 존은 원을 따라 시계 방향으로 훑으며 각 건너는 지점의 소 ID를 적어서 이 지점들을 간결하게 기록하고, 결국 각 수가 정확히 두 번씩 나타나는 \(2N\)개의 수로 이루어진 수열을 얻는다. 어느 지점이 입장 지점이고 어느 지점이 퇴장 지점인지는 기록하지 않는다.

건너는 지점들의 지도를 보며, 농부 존은 여러 소 쌍이 낮 동안 서로 몇 번이나 경로가 교차할지 궁금해한다. 소 \(a\)의 입장 지점에서 퇴장 지점으로 가는 경로가 소 \(b\)의 입장 지점에서 퇴장 지점으로 가는 경로와 반드시 교차해야 한다면, 소 쌍 \((a,b)\)를 "교차하는" 쌍이라고 부른다. 교차하는 쌍의 총 수를 세는 것을 도와주자.

문제 제공: Brian Dean

문제 제공: Brian Dean

입력의 첫째 줄에는 \(N\) (\(1 \leq N \leq 50,000\))이 주어지고, 다음 \(2N\)개의 줄에는 들판 둘레의 입장 및 퇴장 지점 순서대로 소의 ID가 주어진다.

교차하는 쌍의 총 수를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Gold