官方题解｜普尔亚的委托

提示1

如果 $N$ 和 $M$ 的范围为 $[3, 1000]$ 如何解决这个问题？

提示2

每个遗迹的坐标具体是多少真的很重要吗？

题目解析

如果 $N$ 和 $M$ 比较小的话，我们可以使用「二维数组」存储地图信息，把所有遗迹在「二维数组」中标注出来，然后在地图上做 $\tt{DFS/BFS}$ 求「连通块」的数量即可。

但是现在 $N$ 和 $M$ 很大，我们完整无法去存储整个地图及遗迹的细节。

但是遗迹的坐标具体是多少，真的很重要吗？

不妨设想，这是一个可以放缩的地图。

那么可以发现，对地图放大或者缩小并不会影响其被分成几个部分的结果。

那么其实我们真正需要记录的只是遗迹之间的相对关系。

前后没有遗迹的行和列，并不需要被记录下来，不会影响答案。

所以我们可以使用「坐标离散化」的技巧：
对于每个遗迹我们只需要存储遗迹的坐标以及其前后的行和列就足够了，即：
$\tt{A_i - 1, A_i, A_i + 1\ (1 \le A_i - 1 < A_i + 1 \le N)}$，
$\tt{B_i - 1, B_i, B_i + 1\ (1 \le B_i - 1 < B_i + 1 \le M)}$，
$\tt{C_i - 1, C_i, C_i + 1\ (1 \le C_i - 1 < C_i + 1 \le N)}$，
$\tt{D_i - 1, D_i, D_i + 1\ (1 \le D_i - 1 < D_i + 1 \le M)}$。

这样地图上最多存储 $\tt{6K \times 6K}$ 的信息对于本题 $1 \le K \le 500$ 完全可以使用「二维数组」存储离散化后的地图。

然后将遗迹及其前后的 $X$ 坐标和 $Y$ 坐标分别做离散化处理，保留他们的相对关系。

完成「坐标离散化」后，我们使用离散化后的遗迹对离散化后的地图进行标记，并在离散化后的地图上做 $\tt{DFS/BFS}$ 求「连通块」的数量即可。

AC代码

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

constexpr int dirs[][2] {0, 1, 1, 0, 0, -1, -1, 0};

int compress(vector<int> &a, vector<int> &b, int n) {
    vector<int> v;
    for (auto &x : a) {
        if (x > 1) v.push_back(x - 1);
        v.push_back(x);
        if (x < n) v.push_back(x + 1);
    }
    for (auto &x : b) {
        if (x > 1) v.push_back(x - 1);
        v.push_back(x);
        if (x < n) v.push_back(x + 1);
    }
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
    for (auto &x : a)
        x = lower_bound(begin(v), end(v), x) - begin(v);
    for (auto &x : b)
        x = lower_bound(begin(v), end(v), x) - begin(v);
    return v.size();
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(k), b(k), c(k), d(k);
    for (int i = 0; i < k; ++i)
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    n = compress(a, c, n);
    m = compress(b, d, m);
    vector<vector<int>> mat(n, vector<int>(m));
    for (int i = 0; i < k; ++i)
        for (int x = a[i]; x <= c[i]; ++x)
            for (int y = b[i]; y <= d[i]; ++y)
                mat[x][y] = 1;
    int res = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            if (mat[i][j] == 1) continue;
            queue<pair<int, int>> q;
            q.emplace(i, j);
            mat[i][j] = 1;
            while (!q.empty()) {
                auto [x, y] = q.front(); q.pop();
                for (auto &[dx, dy] : dirs) {
                    int nx = x + dx, ny = y + dy;
                    if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
                    if (mat[nx][ny]) continue;
                    q.emplace(nx, ny);
                    mat[nx][ny] = 1;
                }
            }
            res += 1;
        }
    cout << res << '\n';
    return 0;
}

复杂度分析

坐标离散化的时间复杂度为 $\mathrm{O}(6K \log{6K})$；
离散化后在地图上标注遗迹的复杂度为 $\mathrm{O}(6K^2)$；
在离散化后的地图上做 $\tt{DFS/BFS}$ 求「连通块」的数量复杂度为 $\mathrm{O}(36K^2)$；
总的时间复杂度为 $\mathrm{O}(36K^2)$。