BZOJ1604 [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

在一道usaco的题上wa了三次。我也是厉害。

其实好像有简单做法的。不过我是要脑补一下曼哈顿最小生成树。

对于一个平面图上的点的曼哈顿最小生成树，一定存在一种方案，使得每个点的度数至多为8。也就是说以斜率为0,inf,1,-1的四条直线分出来的八个区域里各有一个点就行了。然后是可以保证的。

于是就是拿俩树状数组扫四遍就行了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int inf = 0x3f3f3f3f;

struct point {
	int x, y, i;
	point() {
		x = -inf, y = -1;
	}
	point(int xo, int yo) {
		x = xo, y = yo;
	}
	inline void init(int ix) {
		scanf("%d%d", &x, &y);
		i = ix;
	}
};

inline bool operator <(const point& a, const point& b) {
	return (a. x < b. x) || (a. x == b. x && a. y < b. y);
}

const int maxn = 100009;
const int maxx = 1e9;

int n, c, r[maxn], sz[maxn], cnt, msz;
int v[maxn], tv, w[maxn], tw;
point a[maxn], ta[maxn], tb[maxn];

int getRoot(int x) {
	register int p, q;
	for (p = r[x]; p ^ r[p]; p = r[p]);
	for (; x ^ p; q = r[x], r[x] = p, x = q);
	return x;
}
inline void join(int u, int v) {
	r[getRoot(u)] = getRoot(v);
}

point btQry(point* t, int p) {
	point s(-inf, -1);
	for (++ p; p; p -= (p & -p))
		if (s < t[p])
			s = t[p];
	return s;
}
void btChg(point* t, int p, point v) {
	for (++ p; p < maxn; p += (p & -p))
		if (t[p] < v)
			t[p] = v;
}

inline bool isNeighbour(const point& a, const point& b) {
	return abs(a. x - b. x) + abs(a. y - b. y) <= c;
}

void span() {
	sort(a, a + n);
	tv = tw;
	for (int i = 0; i < n; ++ i) {
		v[i] = a[i]. y - a[i]. x;
		w[i] = - a[i]. x - a[i]. y;
	}
	sort(v, v + n);
	tv = unique(v, v + n) - v;
	sort(w, w + n);
	tw = unique(w, w + n) - w;
	for (int i = 1; i <= tv || i <= tw; ++ i)
		ta[i] = tb[i] = point();
	for (int i = 0; i < n; ++ i) {
		int p(lower_bound(v, v + tv, a[i]. y - a[i]. x) - v);
		point g(btQry(ta, p));
		if (g. y > -1 && isNeighbour(a[i], a[g. y]))
		   join(a[i]. i, a[g. y]. i);	
		btChg(ta, p, point(a[i]. x + a[i]. y, i));
		p = lower_bound(w, w + tw, - a[i]. x - a[i]. y) - w;
		g = btQry(tb, p);
		if (g. y > -1 && isNeighbour(a[i], a[g. y]))
		   join(a[i]. i, a[g. y]. i);	
		btChg(tb, p, point(a[i]. x - a[i]. y, i));
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d", &n, &c);
	for (int i = 0; i < n; ++ i) {
		a[i]. init(i);
		r[i] = i;
	}
	span();
	for (int i = 0; i < n; ++ i)
		a[i]. x = maxx - a[i]. x;
	span();
	for (int i = 0; i < n; ++ i)
		swap(a[i]. x, a[i]. y);
	span();
	for (int i = 0; i < n; ++ i)
		a[i]. x = maxx - a[i]. x;
	span();
	memset(sz, 0, sizeof(sz));
	for (int i = 0; i < n; ++ i) {
		if (r[i] == i)
			++ cnt;
		++ sz[getRoot(i)];
	}
	for (int i = 0; i < n; ++ i)
		if (r[i] == i && sz[i] > msz)
			msz = sz[i];
	printf("%d %d\n", cnt, msz);
}