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);
}