P15308 [VKOSHP 2025] Big World Politics

你有一张世界地图，表示为一个 $n \times m$ 的矩形。地图上的每个单元格属于 $k$ 个国家之一。每个国家所拥有的单元格集合是四连通的——这意味着，从该国家的任何一个单元格出发，你可以通过向下、向上、向左、向右移动，且不进入其他国家的领土，到达该国家的任何其他单元格。 在这动荡的时代，许多国家相互提出了领土要求。国家 $i$ 认为，包含其所有单元格的、边与地图边缘平行的最小矩形内的所有单元格，都是其历史领土。因此，国家 $i$ 对国家 $j$（$j \neq i$）提出领土要求，当且仅当国家 $j$ 有单元格位于国家 $i$ 的这个最小矩形内。 作为一名专业分析师，你的任务是对于每个国家 $i$，确定它向多少个其他国家提出了领土要求。

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 2 \cdot 10^5$，$1 \le k \le nm \le 2 \cdot 10^6$）—— 分别表示地图的高度、地图的宽度以及不同国家的数量。 接下来的 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行包含 $a_{i1}, a_{i2}, \dots, a_{im}$（$1 \le a_{ij} \le k$）—— 分别表示单元格 $(i,1), (i,2), \dots, (i,m)$ 所属的国家编号。 保证每个国家 $k$ 至少拥有一个单元格。 保证每个国家的单元格集合是四连通的。

输出 $k$ 个整数，其中第 $i$ 个整数表示国家 $i$ 提出领土要求的国家数量。

翻译由 DeepSeek 完成