SGU 177 — Square
矩形切割的题目,我不会矩形切割啊(或者说会但是写出来很恶心),于是写了个神奇的二维二叉单层线段树(不是n棵树,是二叉树,而且不是树套树).这东西单次操作的复杂度应该是O((logn)^2),但是竟然比O(nlogn)的还慢…无语了我都…难道这东西常数比n棵线段树大得多?大到了几千的级别?!囧.
不过还是AC了,内存好大.矩形切割其实最不错=.=,不过没怎么写过.不打算学,线段树也挺好的.
{ SGU 177; Square - sqybi’s code - 线段树}//for my winstyprogram sgu177_sqybi; const nn = 1000;
type treeNode = record x1, y1, x2, y2: integer; c: longint; lazy: boolean; end;
var tree: array[1..nn*nn*4]of treeNode; n, m, i, x1, y1, x2, y2, z: longint; ch: char;
procedure init(x, x1, y1, x2, y2: longint); [...]