Shaping Regions

形成的区域
译 by tim green


　　N个不同的颜色的不透明的长方形(1 <= N <= 1000)被放置在一张宽为A长为B的白纸上。
这些长方形被放置时，保证了它们的边于白纸的边缘平行。
所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。
坐标系统的原点(0,0)设在这张白纸的左下角，而坐标轴则平行于边缘。

PROGRAM NAME: rect1

INPUT FORMAT
每行输入的是放置长方形的方法。
第一行输入的是那个放在底的长方形(即白纸)。
第 1 行:       A ， B 和 N, 由空格分开 (1 <=A, B<=10,000)
第 2 到N+1行:  为五个整数　llx, lly, urx, ury, color　这是一个长方形的左下角坐标，右上角坐标和颜色。
颜色 1和底部白纸的颜色相同。

SAMPLE INPUT (file rect1.in)
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4

OUTPUT FORMAT
输出文件应该包含一个所有能被看到颜色连同该颜色的总面积的清单( 即使颜色的区域不是连续的)，按color的增序顺序。
不要显示没有区域的颜色。

SAMPLE OUTPUT (file rect1.out)
1 91
2 84
3 187
4 38

最初由 luocong 发布

必须用矩阵切割或者离散化+线段树。矩阵切割太麻烦（偶的空间想象力不够），放弃。最终偶用了离散化+线段树来完成。

最初由 luocong 发布
这道题最后给我的感觉是用线段树反而更慢了，其实直接开个大小为 2 * N 的数组反而会快点。线段树属于高级数据结构？只是平衡树而已，感觉还不如我以前写的AVL树复杂。

最初由 RoBa 发布
这类问题可以讨论的吧,monkeycz和我都很感兴趣的哟

最初由 北极星2003 发布
能不能给个地址（递交系统）？
这个题目我要好好学习一下。
说不定明年ACM还有用
用问题再向各位请教

最初由 dREAMtHEATER 发布
老罗似乎要放弃自己的坛子了，也许放弃是件好事.....

最初由 北极星2003 发布
能不能给个地址（递交系统）？
这个题目我要好好学习一下。
说不定明年ACM还有用
用问题再向各位请教

最初由 luocong 发布


像我一样的初学者建议去USACO，它的题比较静电，而且是由浅入深的，涵盖哥哥领域，最爽的是做对了还能看官方的解答……

USACO:
........