题意:给出一个200 * 50000的像素点矩阵，执行50000次操作，每次把一个矩形/圆形/菱形/三角形内的像素点涂成指定颜色，问最后每种颜色的数量。
分析:乍一看,很像用线段树成段更新写,虽然复杂度有点大,但是也想不到其他的方法.这题可以巧妙地运用并查集来涂色.离线,从最后一个倒过来涂色,保证能涂上去的一定不会被覆盖,每次扫描一行,将一条线上的点都合并到右端点.
#include <bits/stdc++.h>
using namespace std; #define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
typedef long long LL;
const int N = 5e4 + 2;
const int INF = 0x3f3f3f3f;
struct DSU {
int rt[N];
void clear(int n) {
fill (rt, rt+n, -1);
}
int Find(int x) {
return rt[x] == -1 ? x : rt[x] = Find (rt[x]);
}
void Union(int x, int y) {
rt[x] = y;
}
}dsu;
struct Point {
char str[20];
int xc, yc, a, b, c;
}p[N];
bool vis[N];
int ans[10];
int n, m, q; int squ(int x) {
return x * x;
} int cal(int x, int y) {
x = abs (x); y = abs (y);
return squ (x) + squ (y);
} int main(void) { //好题
while (scanf ("%d%d%d", &n, &m, &q) == 3) {
memset (ans, 0, sizeof (ans));
for (int i=0; i<q; ++i) {
scanf ("%s%d%d", &p[i].str, &p[i].xc, &p[i].yc);
if (p[i].str[0] == 'R') scanf ("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
else scanf ("%d%d", &p[i].a, &p[i].c);
}
for (int i=0; i<n; ++i) {
dsu.clear (m); memset (vis, false, sizeof (vis));
for (int j=q-1; j>=0; --j) {
int left = 0, right = 0;
if (p[j].str[0] == 'C') {
if (squ (i - p[j].xc) > squ (p[j].a)) continue;
int tmp = (int) sqrt (1.0 * (squ (p[j].a) - squ (i - p[j].xc)));
left = p[j].yc - tmp; right = p[j].yc + tmp;
}
else if (p[j].str[0] == 'D') {
if (i < p[j].xc - p[j].a || i > p[j].xc + p[j].a) continue;
left = p[j].yc - p[j].a + abs (i - p[j].xc); right = p[j].yc + p[j].a - abs (i - p[j].xc);
}
else if (p[j].str[0] == 'R') {
if (i < p[j].xc || i > p[j].xc + p[j].a - 1) continue;
left = p[j].yc; right = p[j].yc + p[j].b - 1;
}
else if (p[j].str[0] == 'T') {
if (i < p[j].xc || i > p[j].xc + (p[j].a + 1) / 2 - 1) continue;
left = p[j].yc - p[j].a / 2 + (i - p[j].xc); right = p[j].yc + p[j].a / 2 - (i - p[j].xc);
}
if (left < 0) left = 0;
if (right >= m) right = m - 1;
int fa, fb = dsu.Find (right);
for (int k=left; k<=right; k=fa+1) { //paint a line
fa = dsu.Find (k);
if (!vis[fa]) {
ans[p[j].c]++; vis[fa] = true;
}
if (fa != fb) dsu.Union (fa, fb);
}
}
}
for (int i=1; i<=9; ++i) {
printf ("%d%c", ans[i], i == 9 ? '\n' : ' ');
}
} return 0;
}