bzoj1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

Description

了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的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均同属一个群．     给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛

Solution

读入坐标后先做一个处理，把横坐标改为x+y，纵坐标改为x-y，这样一来，曼哈顿距离变为了max(|x1-x2|,|y1-y2|)

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

按新的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);
}