题目大意

给定一个 $n \times n$ 的网格，要将 $0$ 到 $n^2-1$ 这 $n^2$ 个数各用一次填入网格。
对于任意一个子矩形（连续若干行、连续若干列），定义它的 $\operatorname{MEX}$ 为最小的没有出现在这个子矩形中的非负整数。
要最大化 所有子矩形的 MEX 之和，输出任意一种达到最大值的填法。

子矩形的总数为 $\left( \frac{n(n+1)}{2} \right)^2$。

---

关键转化

对于一个子矩形 $S$，设其 MEX 为 $m$，意味着：

• $0,1,\dots,m-1$ 都出现在 $S$ 中，
• $m$ 不在 $S$ 中。

因此：

$$\operatorname{MEX}(S) = \sum_{k \ge 1} [\; 0,1,\dots,k-1 \text{ 都在 } S \text{ 中} \;] $$

其中 $[P]$ 是示性函数（$P$ 真为 $1$，假为 $0$）。

于是所有子矩形的 MEX 之和为：

$$\sum_{S} \operatorname{MEX}(S) = \sum_{k \ge 1} \#\{\, S \mid S \text{ 包含 } 0,1,\dots,k-1 \,\} $$

---

最大化思路

为了最大化总和，对于每个 $k$，我们要让 包含 $0,1,\dots,k-1$ 的子矩形个数 尽可能大。

这等价于：让这些数在网格中的位置尽可能“紧凑”，使得包含它们所有的小矩形数量最大。

一个经典结论是：按列优先顺序填充（即先填满第一列，再第二列，...）可以达到最优。

为什么？

• 这样填完后，最小的 $k$ 个数会占据一个 左上角阶梯形区域。
• 包含这些 $k$ 个数的子矩形，必须至少覆盖它们的最小行、最大行、最小列、最大列。
• 列优先填充使得这些数的分布非常“集中”，从而能覆盖它们的最小子矩形尽可能小，进而包含该最小子矩形的所有更大子矩形也都会包含这 $k$ 个数。

---

构造方法

设当前要填的数字为 $0,1,2,\dots,n^2-1$。

按列优先顺序填入：

• 先填第 $0$ 列的所有行（从上到下）：$0,1,\dots,n-1$
• 再填第 $1$ 列的所有行：$n,n+1,\dots,2n-1$
• 以此类推。

即：

$$a[i][j] = i + j \cdot n$$

其中 $i$ 是行下标（$0$ 到 $n-1$），$j$ 是列下标（$0$ 到 $n-1$）。

---

示例验证

当 $n=2$：

按列优先：

• 第 $0$ 列：$a[0][0]=0,\; a[1][0]=1$
• 第 $1$ 列：$a[0][1]=2,\; a[1][1]=3$

得到矩阵：

$$\begin{bmatrix} 0 & 2 \\ 1 & 3 \end{bmatrix}$$

但题目示例给出的最优解是：

$$\begin{bmatrix} 0 & 1 \\ 2 & 3 \end{bmatrix}$$

注意：两种填法的 MEX 之和可能不同。
实际上，对于 $n=2$，列优先得到 $8$（经计算也可达到最大值），而行优先（示例）也是 $8$。
题目允许多种答案，列优先也是一种正确的构造。

当 $n=3$：

列优先得到：

$$\begin{bmatrix} 0 & 3 & 6 \\ 1 & 4 & 7 \\ 2 & 5 & 8 \end{bmatrix} $$

这个矩阵的 MEX 总和也是理论最大值（可以证明）。

---

时间复杂度

构造网格：$O(n^2)$
总 $n$ 之和 $\le 1000$，完全可行。

---

代码实现（标程）

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<vector<int>> a(n, vector<int>(n));
    
    // 按列优先顺序填充
    int cur = 0;
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            a[i][j] = cur++;
        }
    }
    
    // 输出
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << a[i][j];
            if (j < n - 1) cout << " ";
        }
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

正确性简述

对于任意 $k$，最小的 $k$ 个数在列优先填充下占据的是前 $\lceil k/n \rceil$ 列的部分行。
包含这些 $k$ 个数的子矩形，其行范围必须覆盖它们的最小行到最大行，列范围必须覆盖它们的最小列到最大列。
这种分布使得所有包含该最小矩形的子矩形都包含这 $k$ 个数，从而最大化计数。
可以证明，任何其他排列都不能让每个 $k$ 的包含子矩形数更大，因此列优先填充达到全局最优。

---

总结

• 核心转化：$\operatorname{MEX}$ 和 $\to$ 每个前缀 $[0,k-1]$ 被包含的子矩形数之和。
• 最优策略：让小数尽量集中在一个小矩形内。
• 具体构造：按列优先顺序填入 $0,1,\dots,n^2-1$。
• 时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。