NOT A BLOG | sqybi

SGU 177 — Square

Posted on 四月 25th, 2008.

矩形切割的题目,我不会矩形切割啊(或者说会但是写出来很恶心),于是写了个神奇的二维二叉单层线段树(不是n棵树,是二叉树,而且不是树套树).
这东西单次操作的复杂度应该是O((logn)^2),但是竟然比O(nlogn)的还慢…无语了我都…
难道这东西常数比n棵线段树大得多?大到了几千的级别?!囧.

不过还是AC了,内存好大.
矩形切割其实最不错=.=,不过没怎么写过.
不打算学,线段树也挺好的.

{
SGU 177; Square
- sqybi’s code
- 线段树
}
//for my winsty
program 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);
    begin
      tree[x].x1 := x1;
      tree[x].y1 := y1;
      tree[x].x2 := x2;
      tree[x].y2 := y2;
      if (x1 = x2) and (y1 = y2) then exit;
      if x2 - x1 + 1 > y2 - y1 + 1 then begin
        init(x*2, x1, y1, (x1+x2) div 2, y2);
        init(x*2+1, (x1+x2) div 2+1, y1, x2, y2);
      end
      else begin
        init(x*2, x1, y1, x2, (y1+y2) div 2);
        init(x*2+1, x1, (y1+y2) div 2+1, x2, y2);
      end;
    end;

  procedure put(x, y: longint);
    begin
      tree[x].lazy := true;
      tree[x].c := (tree[x].x2 - tree[x].x1 + 1) * (tree[x].y2 - tree[x].y1 + 1) * y;
    end;

  procedure paint(x, x1, y1, x2, y2, z: longint);
    begin
      if (tree[x].x1 >= x1) and (tree[x].y1 >= y1)
       and (tree[x].x2 <= x2) and (tree[x].y2 <= y2) then begin
        put(x, z);
        exit;
      end;
      if (tree[x].x2 < x1) or (tree[x].y2 < y1)
       or (tree[x].x1 > x2) or (tree[x].y1 > y2) then
        exit;
      if tree[x].lazy then begin
        put(x*2, ord(tree[x].c <> 0));
        put(x*2+1, ord(tree[x].c <> 0));
      end;
      tree[x].lazy := false;
      paint(x*2, x1, y1, x2, y2, z);
      paint(x*2+1, x1, y1, x2, y2, z);
      if tree[x*2].lazy and tree[x*2+1].lazy
       and (ord(tree[x*2].c<>0)=ord(tree[x*2+1].c<>0)) then
        put(x, ord(tree[x*2].c<>0))
      else
        tree[x].c := tree[x*2].c + tree[x*2+1].c;
    end;

  function req: longint;
    begin
      req := tree[1].c;
    end;

  begin
    readln(n, m);
    init(1, 1, 1, n, n);
    tree[1].lazy := true;
    tree[1].c := n * n;
    for i:=1 to m do begin
      readln(x1, y1, x2, y2, ch, ch);
      if x1 > x2 then begin
        x1 := x1 xor x2;
        x2 := x1 xor x2;
        x1 := x1 xor x2;
      end;
      if y1 > y2 then begin
        y1 := y1 xor y2;
        y2 := y1 xor y2;
        y1 := y1 xor y2;
      end;     
      z := ord(ch = ‘w’); //white <=> 1
      paint(1, x1, y1, x2, y2, z);
    end;
    writeln(req);
  end.

阅读(120 次)

Make a Comment

Make A Comment: ( 3 so far )

3 Responses to “SGU 177 — Square”

Comments RSS Feed

Where's The Comment Form?