了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的：

1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi – xil+IYi – Yil≤C.

2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群．

给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛

参考题解：

同时因为懒得写splay且set比较清真所以还看了：

（是的在之前我不会用set……）

首先看到曼哈顿距离立刻想到我们可以将其分成四种情况讨论（我们碰到过这样的题，比如）

那么我们经过漫长的讨论之后我们可以得到上面判别式的变体：max( |(Xi+Yi)-(Xj+Yj)|, |(Xi-Yi)-(Xj-Yj)| )<=c。

我们考虑将点坐标(x,y)变为(x+y,x-y)，将max展开得到：

两点为同群满足第一条条件时，当且仅当①|Xi-Xj|<=c且②|Yi-Yj|<=c。

那么我们对X排序（这样单调后O(n)判断①，平衡树中不满足①的点删除即可），用平衡树维护Y的大小关系（lower_bound找到它左右的点与它判断②，其他点显然不用考虑因为如果某点与它为同群则必然与它左/右点同群），满足的点并查集一下即可。

PS：建立一个头和尾防止访问越界，由此可能引发爆int的问题，所以要么判别式移项要么开longlong

#include
     
      #include
      
       #include
       
        using namespace std;const int N=100010;const int INF=2e9+7;inline int read(){    int X=0,w=1;char ch=0;    while(ch<'0'||ch>'9'){
   if(ch=='-')w=-1;ch=getchar();}    while(ch>='0'&&ch<='9')X=(X<<1)+(X<<3)+ch-'0',ch=getchar();    return X*w;}struct point{    int x,y;    bool operator < (const point& a)const{        return x
        
         
          s;multiset
          
            ::iterator it;int fa[N],sz[N],n,c;inline int find(int x){ return (fa[x]==x)?x:fa[x]=find(fa[x]);}inline void unionn(int a,int b){ if(a!=b){fa[a]=b;sz[b]+=sz[a];}}int main(){ n=read(),c=read(); for(int i=1;i<=n;i++){ int x=read(),y=read(); p[i].x=x+y,p[i].y=x-y,fa[i]=i,sz[i]=1; } sort(p+1,p+n+1); s.insert((point){INF,0}),s.insert((point){-INF,0}); int front=1; for(int i=1;i<=n;i++){ while(p[i].x-c>p[front].x){ s.erase(s.lower_bound((point){p[front].y,front})); front++; } it=s.lower_bound((point){p[i].y,i}); point r=*it,l=*(--it); if(r.x-c<=p[i].y)unionn(find(r.y),find(i)); if(p[i].y-c<=l.x)unionn(find(l.y),find(i)); s.insert((point){p[i].y,i}); } int ans=0,maxn=0; for(int i=1;i<=n;i++){ if(fa[i]==i){ ans++; maxn=max(maxn,sz[i]); } } printf("%d %d\n",ans,maxn); return 0;}
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++