题意:链接

方法: Treap

解析:

前几道资格赛的题水的不行，这道Gold的题就够分量辣。

首先这个曼哈顿距离啥的肯定能做文章，怎么转化是个问题，自己玩了一会没玩出来，就查了查曼哈顿距离的转化，发现这个玩意转化之后就变得有思路多了，所以这数学本领还是非常重要啊=-=

先看曼哈顿距离的定义

|x1−x2|+|y1−y2|

拆绝对值

x1−x2+y1−y2或x1−x2+y2−y1

x2−x1+y1−y2或x2−x1+y2−y1

即|x1+y1−(x2+y2)|或|x1−y1−(x2−y2)|

设x1+y1为x′，x1−y1为y′

则|x1′−x2′|或|y1′−y2′|

所以原要求1转化为

max(|x1′−x2′|,|y1′−y2′|)<=c

这样的二维的东西显然排序一下降一维。

按x’排序后。维护一个x’的队列，再对y’维护一个平衡树即可了。

至于要求2，即是并查集，也就是说平衡树每一次拿出来前驱后继维护下并查集即可。

y’显然可能反复，又维护并查集我们须要拿出来标号。所以平衡树须要多维护一个no，所以再删除的时候我们要找到v与no都跟要删除的目标节点同样的节点删除。

（前驱写挫WA一次= =！

代码:

#include <ctime>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 100010

using namespace std;

int fa[N];

int q[N];

int tot;

int root;

int cnt[N];

struct node

{

    int l,r,w,v,no,rnd,siz;

}tr[N];

void pushup(int rt)

{

    tr[rt].siz=tr[tr[rt].l].siz+tr[tr[rt].r].siz+tr[rt].w;

}

void rturn(int &rt)

{

    int t=tr[rt].l;

    tr[rt].l=tr[t].r;

    tr[t].r=rt;

    tr[t].siz=tr[rt].siz;

    pushup(rt);

    rt=t;

}

void lturn(int &rt)

{

    int t=tr[rt].r;

    tr[rt].r=tr[t].l;

    tr[t].l=rt;

    tr[t].siz=tr[rt].siz;

    pushup(rt);

    rt=t;

}

void insert(int &rt,int v,int no)

{

    if(!rt)

    {

        rt=++tot;

        tr[rt].siz=1,tr[rt].no=no,tr[rt].rnd=rand();

        tr[rt].v=v,tr[rt].w=1;

        return;

    }

    tr[rt].siz++;

    if(v<=tr[rt].v)

    {

        insert(tr[rt].l,v,no);

        if(tr[tr[rt].l].rnd<tr[rt].rnd)rturn(rt);

    }else

    {

        insert(tr[rt].r,v,no);

        if(tr[tr[rt].r].rnd<tr[rt].rnd)lturn(rt);

    }

}

void del(int &rt,int v,int no)

{

    if(!rt)return;

    tr[rt].siz--;

    if(tr[rt].v==v&&tr[rt].no==no)

    {

        if(tr[rt].l*tr[rt].r==0){rt=tr[rt].l+tr[rt].r;return;}

        else

        {

            if(tr[tr[rt].l].rnd<tr[tr[rt].r].rnd)

            {

                rturn(rt);

                del(rt,v,no);

            }else

            {

                lturn(rt);

                del(rt,v,no);

            }

        }

    }else if(v<tr[rt].v)

    {

        del(tr[rt].l,v,no);

    }else del(tr[rt].r,v,no);

}

int ans;

void q_pre(int rt,int v)

{

    if(!rt)return;

    if(v>=tr[rt].v)

    {

        ans=rt;

        q_pre(tr[rt].r,v);

    }else q_pre(tr[rt].l,v);

}

void q_sub(int rt,int v)

{

    if(!rt)return;

    if(v<tr[rt].v)

    {

        ans=rt;

        q_sub(tr[rt].l,v);

    }else q_sub(tr[rt].r,v);

}

struct point

{

    int x,y;

}pt[N];

int n,c;

int find(int x)

{

    if(x!=fa[x])return fa[x]=find(fa[x]);

    return x;

}

int cmp(point a,point b)

{

    if(a.x==b.x)return a.y<b.y;

    return a.x<b.x;

}

int main()

{

    scanf("%d%d",&n,&c);

    for(int i=1;i<=n;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        pt[i].x=x+y,pt[i].y=x-y;

        fa[i]=i;

    }

    sort(pt+1,pt+n+1,cmp);

    int head=1,tail=0;

    for(int i=1;i<=n;i++)

    {

        while(head<=tail&&pt[i].x-pt[q[head]].x>c)

        {

            del(root,pt[q[head]].y,q[head]);

            head++;

        }

        ans=0;

        q_pre(root,pt[i].y);

        int tmp=ans;

        if(tmp!=0)

        {

            if(pt[i].y-tr[tmp].v<=c)

            {

                if(find(i)!=find(tr[tmp].no))

                {

                    fa[find(i)]=find(tr[tmp].no);

                }

            }

        }

        ans=0;

        q_sub(root,pt[i].y);

        tmp=ans;

        if(tmp!=0)

        {

            if(tr[tmp].v-pt[i].y<=c)

            {

                if(find(i)!=find(tr[tmp].no))

                {

                    fa[find(i)]=find(tr[tmp].no);

                }

            }

        }

        insert(root,pt[i].y,i);

        q[++tail]=i;

    }

    int ma=0,print=0;

    for(int i=1;i<=n;i++)

    {

        int fx=find(i);

        if(!cnt[fx])

        {

            print++;

        }

        cnt[fx]++;

        if(cnt[fx]>ma)ma=cnt[fx];

    }

    printf("%d %d\n",print,ma);

}