Description

Solution

不难证明，新的|x1-x2|就是原来的|x1-x2+y1-y2|,|y1-y2|就是|x1-x2-y1+y2|，数学好的可以用绝对值不等式证明

/*蒟蒻数学不好，段考只有113*/

按新的X排序后维护一个队列，使得队头和队尾的差不大于C，y另建平衡树

在平衡树里找最大不大于y的数，如果和y的差不大于C，就用并查集合并。最后把y加入平衡树中

写不来平衡树，multiset来一发

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<cstdlib>
#define maxn 100010
#define ll long long
#define inf 10000000000LL
using namespace std;

struct data{
ll x,y;int id;
}pos[maxn];

multiset<data>b;
set<data>::iterator it;
int n,c,fa[maxn],ans,tot[maxn],ans2;

inline bool operator<(data a,data b){
return a.y<b.y;
}

inline int read(){         //第一次用读入优化
int f=1,x=0;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;
}

inline bool cmp(data x,data y){
return x.x<y.x;
}

int find(int x){    //并查集
return x==fa[x]?x:fa[x]=find(fa[x]);
}

void init(){
n=read(),c=read();
for(int i=1;i<=n;++i){
int x=read(),y=read();
pos[i].x=x+y;
pos[i].y=x-y;
pos[i].id=i;
}
sort(pos+1,pos+n+1,cmp);
}

void solve(){
b.insert((data){0,inf,0});
b.insert((data){0,-inf,0});
int now=1;b.insert(pos[1]);
for(int i=2;i<=n;++i){
while(pos[i].x-pos[now].x>c){    //队列维护
b.erase(b.find(pos[now]));
++now;
}
it=b.lower_bound(pos[i]);     //查找y不大于pos[i].y的点的位置
data r=*it,l=*--it;           //注意有前后两个
if(pos[i].y-l.y<=c){
int p=find(pos[i].id),q=find(l.id);
if(p!=q){
fa[p]=q;
ans--;
}
}
if(r.y-pos[i].y<=c){
int p=find(r.id),q=find(pos[i].id);
if(p!=q){
fa[p]=q;--ans;
}
}
b.insert(pos[i]);        //加入平衡树
}
}

int main(){
init();
for(int i=1;i<=n;++i)fa[i]=i;
ans=n;
solve();
for(int i=1;i<=n;++i)
tot[find(i)]++;
ans2=0;
for(int i=1;i<=n;++i)
ans2=max(ans2,tot[i]);
printf("%d %d\n",ans,ans2);
}