Weird Sum
Contest: Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 1400
Tags: combinatorics, data structures, geometry, math, matrices, sortings

Egor has a table of size $$$n \times m$$$, with lines numbered from $$$1$$$ to $$$n$$$ and columns numbered from $$$1$$$ to $$$m$$$. Each cell has a color that can be presented as an integer from $$$1$$$ to $$$10^5$$$.

Let us denote the cell that lies in the intersection of the $$$r$$$-th row and the $$$c$$$-th column as $$$(r, c)$$$. We define the manhattan distance between two cells $$$(r_1, c_1)$$$ and $$$(r_2, c_2)$$$ as the length of a shortest path between them where each consecutive cells in the path must have a common side. The path can go through cells of any color. For example, in the table $$$3 \times 4$$$ the manhattan distance between $$$(1, 2)$$$ and $$$(3, 3)$$$ is $$$3$$$, one of the shortest paths is the following: $$$(1, 2) \to (2, 2) \to (2, 3) \to (3, 3)$$$.

Egor decided to calculate the sum of manhattan distances between each pair of cells of the same color. Help him to calculate this sum.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \le m$$$, $$$n \cdot m \leq 100\,000$$$) — number of rows and columns in the table.

Each of next $$$n$$$ lines describes a row of the table. The $$$i$$$-th line contains $$$m$$$ integers $$$c_{i1}, c_{i2}, \ldots, c_{im}$$$ ($$$1 \le c_{ij} \le 100\,000$$$) — colors of cells in the $$$i$$$-th row.

Output format:
Print one integer — the the sum of manhattan distances between each pair of cells of the same color.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample there are three pairs of cells of same color: in cells $$$(1, 1)$$$ and $$$(2, 3)$$$, in cells $$$(1, 2)$$$ and $$$(2, 2)$$$, in cells $$$(1, 3)$$$ and $$$(2, 1)$$$. The manhattan distances between them are $$$3$$$, $$$1$$$ and $$$3$$$, the sum is $$$7$$$.

Example input:
2 3
1 2 3
3 2 1

Example output:
7

Example input:
3 4
1 1 2 2
2 1 1 2
2 2 1 1

Example output:
76

Editorial:
We note that the manhattan distance between cells $$$(r_1, c_1)$$$ and $$$(r_2, c_2)$$$ is equal to $$$|r_1-r_2|+|c_1-c_2|$$$. For each color we will compose a list of all cells $$$(r_0, c_0), \ldots, (r_{k-1}, c_{k-1})$$$ of this color, compute the target sum for this color, and sum up the answers for all colors. The sum is equal:
$$$$$$ \sum_{i=0}^{k-1} \sum_{j=i+1}^{k-1} |r_i - r_j| + |c_i - c_j| = \left(\sum_{i=0}^{k-1} \sum_{j=i+1}^{k-1} |r_i - r_j|\right) + \left(\sum_{i=0}^{k-1} \sum_{j=i+1}^{k-1} |c_i - c_j|\right) $$$$$$
We will compute the first sum, the second sum is analogous. Let an array $$$s$$$ be equal to $$$r$$$, but sorted in increasing order. Then:
$$$$$$ \sum_{i=0}^{k-1} \sum_{j=i+1}^{k-1} |r_i - r_j| = \sum_{i=0}^{k-1} \sum_{j=i+1}^{k-1} s_j - s_i = \left(\sum_{i=0}^{k-1} \sum_{j=i+1}^{k-1} s_j\right) + \left(\sum_{i=0}^{k-1} \sum_{j=i+1}^{k-1} -s_i\right) $$$$$$
The value $$$s_j$$$ occurs in the first double sum exactly $$$j$$$ times, the value $$$-s_i$$$ occurs in the second sum exactly $$$k-1-i$$$ times. Then, the value is equal to:
$$$$$$ \sum_{j=0}^{k-1} js_j + \sum_{i=0}^{k-1} -(k-1-i)s_i = \sum_{i=0}^{k-1} (2i+1-k)s_i $$$$$$
The last sum can be computed in $$$O(k)$$$, the time complexity to sort an array is $$$O(k \log k)$$$. The overall complexity is $$$O(nm\log(nm))$$$. We can also sort arrays of coordinates by adding cells to lists in the right order. This yields an $$$O(nm)$$$ solution.