이상한 합

면접 대비

시간 제한3초메모리 제한1024 MB

요약

격자의 셀마다 색깔이 주어질 때, 같은 색을 가진 모든 셀 쌍의 맨해튼 거리 합을 구합니다.

난이도: 보통10점 중 5점
유형: 해시맵, 정렬, 누적 합
정답자: 아직 제출이 없습니다

문제

Egor에게 $n$ 행 $m$ 열의 표가 있다. 행은 1번부터 $n$ 번까지, 열은 1번부터 $m$ 번까지 번호가 매겨져 있다. 각 칸은 1 이상 $10^9$ 이하의 정수로 나타낼 수 있는 색으로 칠해져 있다.

$r$ 행 $c$ 열에 있는 칸을 $(r, c)$ 로 표기한다. 두 칸 $(r_1, c_1)$ 과 $(r_2, c_2)$ 의 맨해튼 거리는 변을 공유하는 연속된 칸을 따라 이동해 두 칸을 잇는 최단 경로의 길이이다. 경로는 어떤 색의 칸을 지나도 된다. 예를 들어 $(1, 2)$ 와 $(3, 3)$ 의 맨해튼 거리는 3이고, 최단 경로 중 하나는 $(1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$ 이다.

Egor는 같은 색을 가진 칸들의 모든 쌍에 대해 맨해튼 거리를 구해 더하려 한다. 이 합을 계산하라.

입력

첫 줄에 정수 $n$ 과 $m$ 이 주어진다 ( $1 \leq n \leq m$ , $n \cdot m \leq 500000$ ). 각각 표의 행 수와 열 수이다.

다음 $n$ 개 줄에는 표의 각 행이 한 줄씩 주어진다. $i$ 번째 줄에는 $i$ 행 칸들의 색 $c_{i1}, c_{i2}, \ldots, c_{im}$ 이 정수 $m$ 개로 주어진다 ( $1 \leq c_{ij} \leq 10^9$ ).

출력

같은 색을 가진 칸 쌍들의 맨해튼 거리 합을 정수 하나로 출력한다.

힌트

첫 번째 입력 예제에서 같은 색을 가진 칸 쌍은 세 개이다. $(1, 1)$ 과 $(2, 3)$ , $(1, 2)$ 와 $(2, 2)$ , $(1, 3)$ 과 $(2, 1)$ 이다. 이들의 맨해튼 거리는 각각 3, 1, 3이므로 합은 7이다.

예제3

예제 1
입력
```
2 3
1 2 3
3 2 1
```
예상 출력
```
7
```
예제 2
입력
```
3 4
1 1 2 2
2 1 1 2
2 2 1 1
```
예상 출력
```
76
```

예제 3

입력

예상 출력