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("%d\n", ans[9]);}return 0;}