Задача №114663. Странная сумма
У Егора есть табличка \(n \times m\), где строки пронумерованы от \(1\) до \(n\) сверху вниз, а столбцы пронумерованы с \(1\) до \(m\) слева направо. Каждая клетка таблички покрашена в некоторый цвет, где цвета пронумерованы целыми числами от \(1\) до \(10^9\).
Будем обозначать клетку, которая находится на пересечении \(r\)-й строки и \(c\)-го столбца, как \((r, c)\). Определим манхэттенское расстояние между клетками \((r_1, c_1)\) и \((r_2, c_2)\) как длину кратчайшего пути между этими клетками, в котором любые две соседние клетки имеют общую сторону. Например, в таблице \(3 \times 4\) манхэттенское расстояние между клетками \((1, 2)\) и \((3, 3)\) равно \(3\), и один из кратчайших путей имеет вид \((1, 2) \to (2, 2) \to (2, 3) \to (3, 3)\). Обратите внимание, что путь может проходить по клеткам любого цвета.
У Егора возникло желание посчитать сумму манхэттенских расстояний по всем парам клеток одного цвета. Помогите Егору — вычислите эту сумму.
Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \leq n \le m\), \(n \cdot m \leq 500000\)) — число строк и столбцов таблички.
Следующие \(n\) строк описывают соответствующие строки таблицы. \(i\)-я строка содержит \(m\) чисел \(c_{i1}, c_{i2}, \ldots, c_{im}\) (\(1 \le c_{ij} \le 10^9\)) — цвета клеток в \(i\)-м ряду таблицы.
Выведите одно число — искомую сумму.
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп.
Пусть \(C\) — максимальный по номеру цвет, который встречается в табличке.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(n \cdot m\) | \(C\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия | |
| 1 | 23 | – | \(n \cdot m \le 1000\) | – | 0 | |
| 2 | 17 | \(n=1\) | – | – | ||
| 3 | 15 | \(n=2\) | – | – | ||
| 4 | 20 | – | – | \(C \le 2\) | ||
| 5 | 25 | – | – | – | 0 – 4 | |
В первом примере есть три пары клеток с одинаковым цветом: в координатах \((1, 1)\) и \((2, 3)\), в координатах \((1, 2)\) и \((2, 2)\), в координатах \((1, 3)\) и \((2, 1)\). Соответствующие манхеттенские расстояния равны \(3\), \(1\) и \(3\), их сумма равна \(7\).
2 3 1 2 3 3 2 1
7
3 4 1 1 2 2 2 1 1 2 2 2 1 1
76
4 4 1 1 2 3 2 1 1 2 3 1 2 1 1 1 2 1
129