题解 P2906 【[USACO08OPEN]牛的街区Cow Neighborhoods】

· · 题解

\Large\texttt{My Blog}

Description

题目链接：Luogu 2906

了解奶牛们的人都知道，奶牛喜欢成群结队。观察约翰的 n 只奶牛，你会发现她们已经结成了几个“群”。每只奶牛在吃草的时候有一个独一无二的位置坐标 (X_i,Y_i)。当满足下列两个条件之一，两只奶牛 i 和 j 是属于同一个群的：

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

请计算有多少个牛群，以及最大的牛群里有多少奶牛。

数据范围：1\le n\le 10^5，1\le X_i,Y_i,C\le 10^9，X_i,Y_i,C\in \mathbb{Z}

Solution

首先我们有一个转化：曼哈顿距离转切比雪夫距离。将一个点的坐标 (x,y) 转化成 (x+y,x-y)，设新点的坐标为 (x',y')，那么原来的曼哈顿距离 \vert x_1-x_2\vert +\vert y_1-y_2\vert 就等于现在的切比雪夫距离 \max(\vert x'_1-x'_2\vert,\vert y'_1-y'_2\vert)。可以通过分类讨论或几何法简单证明成立。

设第 i 个点的新坐标为 (X_i+Y_i,X_i-Y_i)，记为 (x_i,y_i)。那么第 1 个限制会变为：

由于有 \max，我们可以将 (x_i,y_i) 以 x_i 为第一个关键字，y_i 为第二关键字，从小到大排序。对于同一群的奶牛我们用并查集合并。

我们用 \text{set} 维护 y_i（每个点）的值，我们每次在插入第 i 个点时，先把 \text{set} 中所有满足 \vert x_i-x_j\vert>C 的点都删除，然后用 \text{lower_bound} 找到第一个大于等于 y_i 的点，如果满足约束条件就将这两个点合并起来。再找到最后一个小于 y_i 的点，进行相同合并操作。

最后我们证明其他的点不需要和 i 合并。

对于大于等于 y_j 的点 k 满足约束条件 y_k-y_i\le C，那么 y_k-y_j\le y_k-y_i\le C，那么在处理 j 或 k 时一定会把 k 合并进来（这取决于 x_j 和 x_k 的大小），所以不必合并了。对于小于的部分证明同理。

时间复杂度：O(n\cdot\alpha(n)\log n)

Code

#include <cstdio>
#include <algorithm>
#include <set>
typedef std::pair<long long,int> pli;
typedef std::pair<long long,long long> pll;
#define mk std::make_pair

const int N=1e5+5;
int n,C,fa[N],cnt[N];
pll a[N];
std::set<pli> s;

int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y) {
    fa[find(x)]=find(y);
}
int main() {
    scanf("%d%d",&n,&C);
    for(int i=1;i<=n;++i) {
        int X,Y;
        scanf("%d%d",&X,&Y);
        a[i]=mk(X+Y,X-Y),fa[i]=i;
    }
    std::sort(a+1,a+n+1);
    s.insert(mk(-1LL<<60,0)),s.insert(mk(1LL<<60,0));
    s.insert(mk(a[1].second,1));
    for(int l=1,i=2;i<=n;++i) {
        while(a[i].first-a[l].first>C) s.erase(mk(a[l].second,l)),++l;
        std::set<pli>::iterator it=s.lower_bound(mk(a[i].second,0));
        if(it->first-a[i].second<=C) merge(i,it->second);
        --it;
        if(a[i].second-it->first<=C) merge(i,it->second);
        s.insert(mk(a[i].second,i));
    }
    int ans=0,mx=0;
    for(int i=1;i<=n;++i) ans+=(find(i)==i),mx=std::max(mx,++cnt[find(i)]);
    printf("%d %d\n",ans,mx);
    return 0;
}