题意:给出一个200 * 50000的像素点矩阵，执行50000次操作，每次把一个矩形/圆形/菱形/三角形内的像素点涂成指定颜色，问最后每种颜色的数量。

分析:乍一看,很像用线段树成段更新写,虽然复杂度有点大,但是也想不到其他的方法.这题可以巧妙地运用并查集来涂色.离线,从最后一个倒过来涂色,保证能涂上去的一定不会被覆盖,每次扫描一行,将一条线上的点都合并到右端点.

#include 
     
      using namespace std;#define lson l, mid, o << 1#define rson mid + 1, r, o << 1 | 1typedef 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
      
       =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;}