洛谷 - P2906 Cow Neighborhoods G

题面

题目描述

了解奶牛的人都知道奶牛是如何组成「奶牛社区」的。他们观察了 Farmer John 的 $N$ 头奶牛（编号为 $1 \sim N$），它们在 $X$ 和 $Y$ 坐标范围为 $1$ 的牧场上放牧，每头奶牛都在自己唯一的整数直线坐标上。

如果满足以下两个标准中的至少一个，则两头奶牛是邻居：

1. 两只奶牛的曼哈顿距离不超过 $C$，即 $|X_i - x_i| + |Y_i - y_i| \leq C$；
2. 两只奶牛有共同的邻居。即存在一只奶牛 $k$，使 $i$ 与 $k$，$j$ 与 $k$ 均同属一个群。

给定奶牛的位置和距离 $C$，确定「奶牛社区」的数量和最大的「奶牛社区」中的奶牛数量。

例如，考虑下面的牧场。 当 $C = 4$ 时，这个牧场有四个社区：左边的一个大社区，两个大小为 1 的社区，右边有一个巨大的社区，里面有 $60$ 头不同的奶牛。

.....................................*.................
....*...*..*.......................***.................
......*...........................****.................
..*....*..*.......................*...*.******.*.*.....
........................*.............***...***...*....
*..*..*...*..........................*..*...*..*...*...
.....................................*..*...*..*.......
.....................................*..*...*..*.......
...*................*..................................
.*..*............................*.*.*.*.*.*.*.*.*.*.*.
.*.....*..........................*.*.*.*.*.*.*.*.*.*.*
....*..................................................

输入格式

第 $1$ 行包含两个用空格分隔的整数 $N, C$。

第 $2$ 到第 $N + 1$ 行每行包含两个用空格分隔的整数 $X_i, Y_i$，表示一头牛的坐标。

输出格式

共一行，为两个用空格分隔的整数，为「奶牛社区」的数量和最大的「奶牛社区」内牛的数量。

输入输出样例

样例输入 #1

4 2
1 1
3 3
2 2
10 10

样例输出 #1

2 3

样例说明 #1

样例中有 $2$ 个社区，一个由前三头奶牛组成，另一个是最后一头奶牛。因此，最大的社区大小为 $3$。

数据范围与约定

对于 $100\%$ 的数据，$1 \leq N \leq 10^5$，$1 \leq C \leq 10^9$，$1 \leq X_i, Y_i \leq 10^9$，$X_i, Y_i$ 均为整数。

思路

机房巨佬于队曾经教过我们一个小 trick：曼哈顿距离和切比雪夫距离之间的转化。

曼哈顿坐标系是通过将切比雪夫坐标系旋转 $\frac{\pi}{4}$ 后再缩小到原来的一半得到的。那么可以通过将 $(x, y)$ 变为 $(x + y, x - y)$ 得到曼哈顿坐标系。

记题中第 $i$ 个点 $(X_i, Y_i)$ 的切比雪夫坐标为 $(x_i, y_i)$，那么限制 $1$ 可以改写成：

• 两只奶牛的切比雪夫距离不超过 $C$，即 $\max(|x_1 - x_2|, |y_1 - y_2|) \leq C$。

那么可以先以 $x$ 轴坐标为第一关键字，$y$ 轴坐标为第二关键字从小到大排序，并使用并查集合并同一群的奶牛。然后使用 set 维护 $y$ 轴坐标的值，在插入每个点之前将 $x$ 轴坐标不合法的删除，然后使用 lower_bound 找到 $y_i$ 的前驱和后继，如果满足限制则将其与 $y_i$ 合并。最后统计连通块个数和最大连通块大小即可。

代码

#include <iostream>
#include <algorithm>
#include <set>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int n, c, fa[N], cnt[N], ans, max;
std::pair<int, int> points[N];
std::set<std::pair<int, int>> set;

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline void merge(int x, int y) {
    fa[find(x)] = find(y);
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> c;

    for (int i = 1, x, y; i <= n; i++) {
        cin >> x >> y;

        points[i] = std::make_pair(x + y, x - y);
        fa[i] = i;
    }

    std::sort(points + 1, points + 1 + n);

    set.insert(std::make_pair(points[1].second, 1));
    for (int i = 2, l = 1; i <= n; i++) {
        while (points[i].first - points[l].first > c) {
            set.erase(std::make_pair(points[l].second, l));
            l++;
        }

        auto it = set.lower_bound(std::make_pair(points[i].second, 0));

        if (it != set.end() && it->first - points[i].second <= c) {
            merge(i, it->second);
        }

        if (it != set.begin() && points[i].second - (--it)->first <= c) {
            merge(i, it->second);
        }

        set.insert(std::make_pair(points[i].second, i));
    }

    for (int i = 1; i <= n; i++) {
        if (find(i) == i) ans++;

        max = std::max(max, ++cnt[find(i)]);
    }

    cout << ans << ' ' << max << endl;

    return 0;
}