其他的题目题解都很好了，这里提供 F 题的一种我认为更好想到且更容易想明白的思路。

简单思考

首先我们可以考虑如下样例：

2 3 4
1 1 1
1 1 4
1
2
3
4

显然的，输出会是：

5
5
5
6

也就是说，当 的时候，查询的结果是一致的，更形象地说，此时的 。

一般情况

所以，对于任意一个矩阵 ，将其中所有元素去重并从小到大排序好，得到序列 （其中 是原矩阵当中不同数字的个数），也就是说，对于任意一个 的查询，都会有三个情况：

  • ：直接输出 ；
  • ：直接输出 ；
  • ：必然存在一个 使得 ，这时直接输出 对应的结果就好了。

所以我们可以考虑预处理一个映射 ，里面存储所有 的 ，查询时我们只需要二分找到 就好了。

数据处理以及思路

接下来我们考虑怎么预处理这个表。

首先有一个简单的性质，就是 是递增的（ 数组已经排序）。

所以我们可以考虑从小处理到大，也就是从 到 。使用另一个映射 来存储 的坐标，也就是 ，这里空间复杂度是 的，不用担心内存。接着我们建议读取的时候直接进行插入，这样可以确保 时的坐标始终在前（这点可以方便我们后续操作）。

在进行下一步之前，我们先实现一个用于模拟毒扩散的 函数，一个全局的 数组和一个 计数器（记录 增加情况）。

接着我们外层循环遍历 ，内层循环遍历 ，在遍历过程中，我们需要考虑两种情况：

  • ：因为我们的毒在第一行释放，所以无论如何，只要当前坐标的 为否，就可以直接进行 BFS。

  • ：这时我们就要考虑当前坐标的上下左右是否存在 为真的点，有的话就说明这一格是可以被感染到的，于是进行 BFS。

注意：第一行的 BFS 总是最优先的，因为我们的毒使用第一行释放的。所以这里就说明了为什么保证 在前会方便操作，这样我们就可以在一次循环内完成上述两种情况，而不必要遍历两次 。

正确性讨论

对于任意的 ，当我们释放大小为 的毒时，显然会覆盖到 的情况，所以我们可以在 已经覆盖的范围上进行扩展，扩展方式就是依照题意的：在第一行放毒，那我们就先对第一行的点直接进行 BFS，然后再对其他不在第一行的 进行 BFS（先判断四周的 ），所以我们使用全局的计数器和 数组，是因为这样就是自然的保留曾经的所有状态。

时间复杂度分析

注意，这样的双层循环也只是遍历了所有的坐标而已，复杂度是 的，我们主要分析 BFS。

因为我们的 数组是不断扩张的，并不会出现已经标记为 但是之后又回退 的现象。放到我们双重循环遍历坐标点里面来看，实际上就是类似于双指针，二者量级都是相同且同时增加的，只不过是增加的时刻和数量不一样，所以全部的 BFS 加起来的时间复杂度才是 。

综上，预处理时间复杂度是 或者 （带 是考虑到 C++ 可以使用 std::map，最坏时 ），查询一次只有二分的开销，于是总复杂度就是 ，在 下可以不卡常通过。

具体细节可以参考 。

Code

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;

    std::vector<std::vector<int>> a(n + 2, std::vector<int>(m + 2));
    std::map<int, std::vector<pii>> pos;	// 前面提到的存储坐标
    int min_v = INF, max_v = 0;	// 记录一下最值，查询的时候可以进行一点小优化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> a[i][j];
            min_v = std::min(min_v, a[i][j]);
            max_v = std::max(max_v, a[i][j]);
            pos[a[i][j]].push_back({ i, j });	// 读取时直接插入，保证 x = 1 在前
        }
    }
    
    int cur = 0;	// 计数器
    std::map<int, int> cnt;	// 存储对应的数量
    
    std::queue<pii> que;	// BFS 队列，可以开在全局（BFS 的循环退出条件）
  	// vis 开大一格可以避免一些边界的问题（比如后面有 vis[x][y + 1] 之类的）
    std::vector<std::vector<int>> vis(n + 2, std::vector<int>(m + 2));
  	// BFS 不多赘述，就是多判断一步 a[next_x][next_y] > k 检查能否继续扩散
    const auto bfs = [&](const pii& st, int k) {
        vis[st.first][st.second] = 1;
        cur++;
        que.push(st);
        while (que.size()) {
            auto [x, y] = que.front();
            que.pop();

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 1 || ny < 1 || nx > n || ny > m || vis[nx][ny] || a[nx][ny] > k) continue;
                vis[nx][ny] = 1;
                cur++;
                que.push({ nx, ny });
            }
        }
    };

  	// 主要循环逻辑，外层就是前文说到的，主要要注意内层的条件逻辑
    for (const auto& [num, v] : pos) {
        for (const auto& [x, y] : v) {
          	// 在任何时候，都不必对已经标记过的位置进行操作，否则会造成计数器重复计数
            if (!vis[x][y]) {
                if (x == 1) {	// 第一行：先放且可以直接放
                    bfs({ x, y }, num);
                } else {	// 其他：先要确定上下左右能否扩散过来
                    if (vis[x - 1][y] || vis[x + 1][y] || vis[x][y - 1] || vis[x][y + 1]) {
                        bfs({ x, y }, num);
                    }
                }
            }
        }
        cnt[num] = cur;	// 扩散完毕后直接记录存储
    }

    while (q--) {
        int x;
        std::cin >> x;

      	// 直接判断 x 和最值得关系就能获得两个答案，前文也有提到
        if (x >= max_v) {
            std::cout << n * m << "\n";
            continue;
        }

        if (x < min_v) {
            std::cout << "0\n";
            continue;;
        }

      	// 二分找到第一个小于 x 的位置，直接输出
        auto it = cnt.upper_bound(x);
        std::cout << std::prev(it)->second << "\n";
    }
}