note.txt

tongji acm-online judge solution

like 1019 line painting
预处理:
由于数据大要用离散化.本题是离散化的经典教材.
算法:
(1)
枚举每个离散化后的行(或列),把相应行(或列)可以看成是区间的覆盖颜色.
注意覆盖顺序,应该上面的先处理,否则一个线段会重复被盖多次,算法退化.
使用线段树,复杂度 O(N^2logN)
usaco可以ac,但是ural上tle.
本题也是线段树的经典教材.
(2)
矩形树（二维线段树） O(N(logN)^2)
一个矩形节点的分成4个子矩形作为儿子.
(3)
也是枚举每个离散化后的行(或列),把相应行(或列)可以看成是区间的覆盖颜色.
用类似并查集的路径压缩来维护一个每个线段后继next的数组.
O(N^2*a(N)),a(N)是一个阿克曼函数.
参见 朱泽园<<回到起点>> wc2005