[USACO Open08]牛的邻居Cow Neighborhoods解题报告

题目


分析

首先我们来搞一搞这个模型。

和一个点的曼哈顿距离<=C的区域大致长这样:



中间红点就是我们的奶牛君。

如果我们把坐标系转45°,换言之做变换:x’=x+y,y’=x-y,那么这个区域就会变成一个正方形,像这样:



其实就是条件|x1-x2|+|y1-y2|<=C换成了|x1'-x2'|<=C且|y1'-y2'|<=C。可以自行枚举x1,x2,y1,y2的大小关系验证。

把整个坐标系画出来,可能是这样:



如果某头牛在另外一头牛的正方形区域内,它们就相邻。

我们自然就有了一个naive的算法:枚举每两头牛,看它们是否相邻,若相邻就用并查集合并之。然而这个算法是O(N^2*并查集)的,并没有什么卵用……

那怎么办呢?

基础思路就是:我们只需要找离某头牛“最近的一圈”。



假设有一头牛A,其右上方区域内y坐标最小的是B。那么,A的右上方所有和A相邻的牛,一定在B的上方且与B相邻。换言之,A右上方所有和A相邻的牛,都可以由A开始的一条“y坐标最小相邻牛”的连续链到达。

所以我们只需要对每个点,找出其四个象限内y坐标最靠近它的点,并将它们的并查集合并即可。这可以用按y坐标从低到高扫描+线段树完成。只需要写一个象限的即可,其他的可以通过变换坐标做四次得到。

代码

#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define Nil NULL
const int SIZEN=100010;
const int INF=0x7fffffff/2;
class Point{
public:
	int x,y;
	int id;
};
void print(const Point &p){
	cout<<"("<t]t]?lc->t:rc->t;
		}
	}
	void modify(int x,int g){//新加一个横坐标为x的g号点
		if(x>r||xmodify(x,g);
			rc->modify(x,g);
			push_up();
		}
	}
	int query(int a,int b){
		if(a>r||b=a&&r<=b) return t;
		int g1=lc->query(a,b),g2=rc->query(a,b);
		return P[g2]l=a,p->r=b;
	if(a==b){
		p->lc=p->rc=Nil;
		p->t=0;
	}
	else{
		int mid=(a+b)/2;
		p->lc=build(a,mid);
		p->rc=build(mid+1,b);
		p->t=0;
	}
	return p;
}
int ufs[SIZEN]={0};
int size[SIZEN]={0};
int grand(int x){
	return !ufs[x]?x:ufs[x]=grand(ufs[x]);
}
void merge(int a,int b){
	int ga=grand(a),gb=grand(b);
	if(ga==gb) return;
	ufs[ga]=gb;
	size[gb]+=size[ga];
}
int X[SIZEN];
Point Q[SIZEN];
void make_nearest(void){
	P[0].x=P[0].y=-INF;
	int tot=0;
	for(int i=1;i<=N;i++) X[tot++]=P[i].x;
	sort(X,X+tot);
	tot=unique(X,X+tot)-X;
	Node *root=build(0,tot-1);
	memcpy(Q,P,sizeof(Q));
	sort(Q+1,Q+1+N);
	for(int i=1;i<=N;i++){
		int l=lower_bound(X,X+tot,Q[i].x-C)-X;
		int r=upper_bound(X,X+tot,Q[i].x)-X-1;
		int q=root->query(l,r);
		if(q&&abs(P[q].y-Q[i].y)<=C) merge(Q[i].id,q);
		root->modify(lower_bound(X,X+tot,Q[i].x)-X,Q[i].id);
	}
}
void work(void){
	for(int i=1;i<=N;i++) size[i]=1;
	for(int c1=-1;c1<=1;c1+=2){
		for(int c2=-1;c2<=1;c2+=2){
			for(int i=1;i<=N;i++){
				P[i].x*=c1;
				P[i].y*=c2;
			}
			make_nearest();
		}
	}
	int cnt=0,mx=0;
	for(int i=1;i<=N;i++){
		if(ufs[i]==0){
			cnt++;
			mx=max(mx,size[i]);
		}
	}
	printf("%d %d\n",cnt,mx);
}
void read(void){
	scanf("%d%d",&N,&C);
	LL x,y;
	for(int i=1;i<=N;i++){
		scanf("%d%d",&x,&y);
		P[i].x=x+y,P[i].y=x-y;
		P[i].id=i;
	}
}
int main(){
	freopen("nabor.in","r",stdin);
	freopen("nabor.out","w",stdout);
	read();
	work();
	return 0;
}


ps:我以前还左手CDQ右手单调队列……现在就只会扫描线+线段树了,药丸呐药丸

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注