hdu 4056 并查集处理线段树染色问题

这题方法很好，把询问离线倒着处理，当前的染色就一定有效。

分析一下全部染完并查集是O(n)的。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 50005;
int n, m, Q;
char op[maxn][15];
int x[maxn], y[maxn], a[maxn], b[maxn], c[maxn];
int ans[11];
struct Set {
	int f[maxn], vis[maxn];
	void init(int n) {
		for (int i = 0; i <= n; i++)
			f[i] = i, vis[i] = 0;
	}
	int find(int x) {
		return x == f[x] ? x : f[x] = find(f[x]);
	}
	void gao(int l, int r, int c) {
		int rx = find(l), ry;
		for (int i = r; i >= l; i = ry - 1) {
			ry = find(i);
			if (!vis[ry]) {
				vis[ry] = 1;
				ans[c]++;
			}
			if (rx != ry)
				f[ry] = rx;
		}
	}
} p;
int F(int x) {
	return x > 0 ? x : -x;
}
int main() {
	int i, j;
	while (~scanf("%d%d%d", &n, &m, &Q)) {
		for (i = 0; i < Q; i++) {
			scanf("%s%d%d%d%d", op[i], &x[i], &y[i], &a[i], &b[i]);
			if (op[i][0] == 'R')
				scanf("%d", &c[i]);
		}
		memset(ans, 0, sizeof(ans));
		for (i = 0; i < n; i++) {
			int l, r, col;
			p.init(m);
			for (j = Q - 1; j >= 0; j--) {
				col = b[j];
				if (op[j][0] == 'R') {
					col = c[j];
					if (i < x[j] || i >= x[j] + a[j])
						continue;
					l = y[j], r = y[j] + b[j] - 1;

				} else if (op[j][0] == 'C') {
					if (F(i - x[j]) > a[j])
						continue;
					int tmp = a[j] * a[j] - (i - x[j]) * (i - x[j]);
					int d = (int) (sqrt(tmp + 0.5));
					l = y[j] - d;
					r = y[j] + d;
				} else if (op[j][0] == 'D') {
					if (F(i - x[j]) > a[j])
						continue;
					int d = a[j] - F(i - x[j]);
					l = y[j] - d, r = y[j] + d;
				} else if (op[j][0] == 'T') {
					if (i - x[j] >= (a[j] + 1) / 2 || i < x[j])
						continue;
					int d = (a[j] - 1) / 2 - (i - x[j]);
					l = y[j] - d, r = y[j] + d;

				}
				l = max(l, 0);
				r = min(r, m - 1);
				p.gao(l, r, col);
				//	puts("~~");
			}
		}
		for (int i = 1; i < 9; i++)
			printf("%d ", ans[i]);
		printf("%dn", ans[9]);
	}
	return 0;
}

最后

以上就是体贴大碗为你收集整理的hdu 4056 并查集处理线段树染色问题的全部内容，希望文章能够帮你解决hdu 4056 并查集处理线段树染色问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。