【POJ 3241】Object Clustering 曼哈顿距离最小生成树

http://poj.org/problem?id=3241

曼哈顿距离最小生成树模板题。

核心思想是把坐标系转3次，以及以横坐标为第一关键字，纵坐标为第二关键字排序后，从后往前扫。扫完一个点就把它插到树状数组的y-x位置上，权值为x+y。查询时查询扫过的所有点满足ydone-xdone>=ynow-xnow时，直接是树状数组中的的一个后缀区间，从后往前扫保证了区间内的这些点都在当前点的y轴向右扫45度的范围内。树状数组实现查询x+y的最小值，以及此最小值对应原数组中的位置，方便建图连边。

模板是抄的别人的QAQ

时间复杂度$O(nlog n)$

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100003;
int in() {
	int k = 0, fh = 1; char c = getchar();
	for(; c < '0' || c > '9'; c = getchar())
		if (c == '-') fh = -1;
	for(; c >= '0' && c <= '9'; c = getchar())	
		k = (k << 3) + (k << 1) + c - '0';
	return k * fh;
}

struct Point {
	int x, y, id;
	bool operator < (const Point &A) const {
		return x == A.x ? y < A.y : x < A.x;
	}
} P[N];
struct Bits {
	int mn, pos;
	void init() {mn = 0x7fffffff; pos = -1;}
} bit[N];
int tot;
struct Edge {
	int u, v, dis;
	bool operator < (const Edge &A) const {
		return dis < A.dis;
	}
} E[N << 2];
void add(int a, int b, int c) {E[++tot] = (Edge) {a, b, c};}

int n, fa[N], k;
int find(int x) {
	if (fa[x] == x) return x;
	fa[x] = find(fa[x]); return fa[x];
}

int dist(int x, int y) {
	return abs(P[x].x - P[y].x) + abs(P[x].y - P[y].y);
}

void update(int x, int num, int pos) {
	for(; x; x -= (x & (-x)))
		if (num < bit[x].mn)
			bit[x].mn = num, bit[x].pos = pos;
}

int m;
int query(int x) {
	int ans = 0x7fffffff, pos = -1;
	for(x; x <= m; x += (x & (-x)))
		if (bit[x].mn < ans)
			ans = bit[x].mn, pos = bit[x].pos;
	return pos;
}

int a[N], H[N], cnt;
int solve() {
	for(int change = 0; change < 4; ++change) {
		if (change == 1 || change == 3)
			for(int i = 1; i <= n; ++i) swap(P[i].x, P[i].y);
		else if (change == 2)
			for(int i = 1; i <= n; ++i) P[i].x = -P[i].x;
		
		sort(P + 1, P + n + 1);
		for(int i = 1; i <= n; ++i)
			a[i] = H[i] = P[i].y - P[i].x;
		cnt = n;
		sort(H + 1, H + cnt + 1);
		cnt = unique(H + 1, H + cnt + 1) - H;
		for(int i = 1; i <= cnt; ++i) bit[i].init();
		int pos, tmp; m = cnt;
		for(int i = n; i > 0; --i) {
			pos = lower_bound(H + 1, H + cnt, a[i]) - H;
			tmp = query(pos);
			if (tmp != -1)
				add(P[i].id, P[tmp].id, dist(i, tmp));
			update(pos, P[i].x + P[i].y, i);
		}
	}
	sort(E + 1, E + tot + 1);
	cnt = n - k;
	for(int i = 1; i <= n; ++i) fa[i] = i;
	int u, v;
	for(int i = 1; i <= tot; ++i) {
		u = find(E[i].u); v = find(E[i].v);
		if (u != v) {
			--cnt;
			fa[u] = v;
			if (cnt == 0) return E[i].dis;
		}
	}
}

int main() {
	while (~scanf("%d%d", &n, &k)) {
		tot = 0;
		for(int i = 1; i <= n; ++i) {
			P[i].x = in(); P[i].y = in();
			P[i].id = i;
		}
		printf("%d
", solve());
	}
	return 0;
}