2010年02月21日星期日.sgu177 平面四叉树
This is my first problem solving report in English,sorry for my poor English.
sgu177: I know 3 ways to solve this problem.
1.quad tree of plane :this is a good and straight forward solution
2.segment trees covers segment trees :less efficient than quadtree,but easy to implement
3.with the special characteristic of this problem,we can dye the plane with opposite
order of the input,and if one grid is colored it cannot be colored again.
The 1st solution can be used extensively.
Quite a lot of the plane query problem can be solve by it.And it also have more
applications in real, such as 3D game programming,computational geometry.
So if you don't know it,I suggest you look the code below.It will be helpful
Though the solution is quite slow in this problem....
The 3rd solution is very smart,you can look here
http://www.briefdream.com/sgu-177/
for a complete code.
I think the original intention of this problem is to practice quadtree,the memory is
just OK when I used quadtree.
sgu177：就我所知，此题有3中解法。
1.平面四叉树：这是一个平面问题的直觉通解。
2.线段树套树，更好写一点，效率稍差，只是常数级别的差距。
3.倒序染色。从后向前染色，如果一个格子已经被染过色的，那么就不必再被染第二遍。
利用这个性质，可以得到一个聪明的解法。具体代码看这里。
http://www.briefdream.com/sgu-177/
我认为这题的本意就是为了练习一下四叉树，四叉树再平面询问的问题上，可以有非常多的应用。
有些需要很巧妙的思考的问题可以直接用四叉树暴力。
而且四叉树在编码，计算几何，计算机图形学，游戏编程上都有很广泛的应用，有可能的话，我
建议自己实现一下。
本题内存比较紧，int超内存的话，可以用short搞一下。
1
2 const int N = 1001;
3 struct node {
4 short ux, uy, dx, dy;
5 char c;
6 node *pt[4];
7 } pool[N * N * 2], *root;
8
9 int top, n, m;
10 void build(node * root, short ux, short uy, short dx, short dy)
11 {
12 //root->c = 0;
13 root->ux = ux;
14 root->uy = uy;
15 root->dx = dx;
16 root->dy = dy;
17 if (ux == dx && uy == dy) { return; }
18
19 short mx =(ux + dx) >> 1;
20 short my =(uy + dy) >> 1;
21 build(root->pt[0] = &pool[top++], ux, uy, mx, my);
22 if (uy != dy) { build(root->pt[1] = &pool[top++], ux, my + 1, mx, dy); }
23 if (ux != dx) { build(root->pt[2] = &pool[top++], mx + 1, uy, dx, my); }
24 if (ux != dx && uy != dy) {
25 build(root->pt[3] = &pool[top++], mx + 1, my + 1, dx, dy);
26 }
27 }
28
29 char color;
30 int x0,x1,y0,y1;
31 const int NEG = 2;
32 void dye(node * root)
33 {
34 if (root == 0) { return; }
35 if (x0 > root->dx || x1 < root->ux ||
36 y0 > root->dy || y1 < root->uy) { //fast exclude
37 return;
38 }
39 if (x0 <= root->ux && x1 >= root->dx &&
40 y0 <= root->uy && y1 >= root->dy) { //complete cover
41 root->c = color;
42 return;
43 }
44 for (int i = 0;i < 4;i++) { //half cover
45 if (root->pt[i]) {
46 /* I think it is the fatal statement which is used to expand the root color
47 * to the desendants */
48 if (root->c != NEG) {
49 root->pt[i]->c = root->c;
50 }
51 dye(root->pt[i]);
52 }
53 }
54 if (root->c != NEG) {
55 root->c = NEG;
56 }
57 }
58//http://www.cppblog.com/schindlerlee/
59 int statics(node * root)
60 {
61 if (root) {
62 int res = 0;
63 if (root->c == NEG) {
64 for (int i = 0;i < 4;i++) {
65 res += statics(root->pt[i]);
66 }
67 }else if (root->c == 0) {
68 res = (root->dy - root->uy + 1) * (root->dx - root->ux + 1);
69 }
70 return res;
71 }
72 return 0;
73 }
74
75 int main()
76 {
77 int i, j, k, ux,uy,dx,dy;
78 char c;
79 scanf("%d%d", &n, &m);
80 root = &pool[top++], build(root, 1, 1, n, n);
81 while (m--) {
82 scanf("%d %d %d %d %c",&ux,&uy,&dx,&dy,&c);
83 color = (c == 'b');
84 x0 = min(ux,dx), x1 = max(ux,dx);
85 y0 = min(uy,dy), y1 = max(uy,dy);
86 dye(root);
87 }
88 printf("%d\n",statics(root));
89 return 0;
90 }
91
92