奶牛邻居——treap+契比雪夫距离+并查集

题目描述

了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．
每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1~109]；Xi，Yi∈整数．
当满足下列两个条件之一，两只奶牛i和j是属于同一个群的：
1．两只奶牛的曼哈顿距离不超过C(1≤C≤109)，即lXi - Xjl+IYi- Yjl≤C.
2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群．
给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛?

思路：

蒟蒻$fhq Treap$初学，所以代码巨丑，封装的也不美观，导致$insert等操作在main$函数里显得很长，这也是我调了很长时间的原因。

这样问题便简化了：我们按x为第一关键字，$y$为第二关键字排序。把$x$扔进队列里，维护$fhq Treap$，里面存的是区间$[head,i](x[i]-x[head]<=C)$中所有的y值，这样我们找到$fhq Treap中y[i]$的前驱和后继用并查集合并即可。代码比较难打。

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<ctime>
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
using namespace std;
typedef long long LL;
const LL N=100010;
const LL inf=99999999999999999;
struct node
{
    LL x,y;
    LL id;
}cow[N],fir[N];
 
LL ch[N][2],rnk[N],id[N],sz[N],root,x,y,z,cnt;
LL val[N];
LL n,C;
LL ans;
 
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
 
bool cmp(node a,node b)
{
    return a.x==b.x?a.y<b.y:a.x<b.x;
}
 
LL father[N],tot[N];
 
inline LL new_node(LL x,LL pos)
{
    cnt++;
    val[cnt]=x;
    rnk[cnt]=rand();
    sz[cnt]=1;
    id[cnt]=pos;
    return cnt;
}
 
inline void pushup(LL now)
{
    sz[now]=1+sz[lc(now)]+sz[rc(now)];
}
 
inline void split(LL now,LL k,LL &x,LL &y)
{
    if(!now)x=y=0;
    else
    {           
        if(val[now]<=k)x=now,split(rc(now),k,rc(now),y);
        else y=now,split(lc(now),k,x,lc(now));
        pushup(now);
    }
}
 
inline LL merge(LL x,LL y)
{
    if(!x||!y)return x+y;
    if(rnk[x]<rnk[y]){rc(x)=merge(rc(x),y);pushup(x);return x;}
    else {lc(y)=merge(x,lc(y));pushup(y);return y;}
}
 
inline LL kth(LL now,LL k)
{
    while(1)
    {
        if(sz[lc(now)]>=k)now=lc(now);
        else if(sz[lc(now)]+1==k)return now;
        else k-=sz[lc(now)]+1,now=rc(now);
    }
}
 
inline LL find(LL x){return x==father[x]?x:father[x]=find(father[x]);}
 
int main()
{
    //freopen("testdata.in","r",stdin);
    //freopen("bbb.out","w",stdout);
    srand(time(0));
    n=read();C=read();
    for(LL i=1;i<=n;i++)
    {
        LL x=read(),y=read();
        cow[i].id=i;
        cow[i].x=x+y;cow[i].y=x-y;
        fir[i]=cow[i];
    }
    sort(cow+1,cow+1+n,cmp);
    for(LL i=1;i<=n;i++)father[i]=i,tot[i]=1;
    root=new_node(cow[1].y,cow[1].id);
     
    split(root,-inf,x,y);root=merge(merge(x,new_node(-inf,0)),y);
    split(root,inf,x,y);root=merge(merge(x,new_node(inf,n+1)),y);
     
    LL head=1;
    for(LL i=2;i<=n;i++)
    {
        LL curx=cow[i].x,cury=cow[i].y;
    //  cout<<"cur="<<curx<<" "<<cury<<endl;
        while(cow[i].x-cow[head].x>C)
        {
            split(root,cow[head].y,x,z);
            split(x,cow[head].y-1,x,y);
            y=merge(lc(y),rc(y));
            root=merge(merge(x,y),z);
            head++;
        }
        split(root,cury,x,y);
        LL pre=id[kth(x,sz[x])];
        root=merge(x,y);
        split(root,cury-1,x,y);
        LL nxt=id[kth(y,1)];
        root=merge(x,y);
        //cout<<"pre nxt="<<pre<<" "<<nxt<<endl;
         
        if(abs(fir[nxt].y-cury)<=C)
        {
            LL r1=find(nxt),r2=find(cow[i].id);
            if(r1&&r2&&r1!=r2)
            {   
                father[r2]=r1;
                tot[r1]+=tot[r2];tot[r2]=0;
            }
        }
        if(abs(fir[pre].y-cury)<=C)
        {
            LL r1=find(pre),r2=find(cow[i].id);
            if(r1&&r2&&r1!=r2)
            {   
                father[r2]=r1;
                tot[r1]+=tot[r2];tot[r2]=0;
            }
        }
        split(root,cury,x,y);
        root=merge(merge(x,new_node(cury,cow[i].id)),y);        
    }
    LL ans=0;
    LL maxn=0;
    for(LL i=1;i<=n;i++)
    {    
        if(find(i)==i)ans++,maxn=max(maxn,tot[i]);
        //cout<<i<<" "<<find(i)<<" "<<ans<<endl;
    }
    cout<<ans<<" "<<maxn;
}