中文题意

第一行给出一个整数。

接下来给出一个的矩阵，你有种颜料，每次你可以选择一个矩阵中的格点填涂一个小正方形，你选择的格点将会成为这个正方形的左上点，并且每个格点做为左上方点只能选择一次，下一次填涂颜料会把上次的颜色覆盖，初始化矩阵都是没涂过颜色的你可以当作涂了颜色，你需要选择中的全部点，填涂次，问最终状态是给出的矩阵的第一次填涂的颜色有多少种？

Solution

正向思考我们很难处理，显然对于当前状态，之前可填涂的方案有很多很多种，难以固定。

但是我们反向思考的话，我们要求出第一次填涂的颜色可以是那些，你们我找到什么颜色不能第一次填涂，最后把减掉这些颜色，是不是也是同样找到了答案呢。

那么如何寻找不能第一次填涂的颜色，我们找到一种颜色它覆盖的矩阵范围，我们把这个矩阵中填涂次数加，那么对于填涂次数的格点，说明最终矩阵中留下的点，一定不能成为第一次填涂的点，因为你会把它覆盖最起码一次，如果第一次就选择了这个点，后续无法找到覆盖方法保留这个点。

还有一种特例，如果整个矩阵中只有种颜色，你又要填涂次，说明最终颜色一定是最后填涂，使用寻找到的方案数应该是，如果矩阵，直接输出种颜色即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 7;
#define DEBUG(x) cout << #x << ":" << x << '\n'
int a[N][N], n;
int up[N * N], r[N * N], dw[N * N], l[N * N];
int sum[N][N];

int main() {
    scanf("%d", &n);
    memset(up, 0x3f, sizeof up);
    memset(l, 0x3f, sizeof l);
    if (n == 1) { return puts("1"), 0; }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &a[i][j]);
            int x = a[i][j];
            up[x] = min(up[x], i);
            r[x] = max(r[x], j);
            dw[x] = max(dw[x], i);
            l[x] = min(l[x], j);
        }
    }
    int cnt = 0; // 先记录出现了几种颜色
    for (int i = 1; i <= n * n; ++i) {
        if (!r[i])    continue;
        ++cnt;
        ++sum[up[i]][l[i]];
        --sum[up[i]][r[i] + 1];
        --sum[dw[i] + 1][l[i]];
        ++sum[dw[i] + 1][r[i] + 1];
    }
    if (cnt == 1) { return printf("%d\n", n * n - 1), 0; }
    // 二维差分
    unordered_set<int> st;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            if (sum[i][j] >= 2)    st.insert(a[i][j]);
        }
    printf("%d\n", n * n - st.size());
    return 0;
}