Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

线段树套线段树。。不知道哪错了 WA WA WA RE RE RE..

Posted by sddyzjh at 2014-02-13 14:46:31 on Problem 2155
type
  re=record
    val,l,r:longint;
  end;
  tree=record
    l,r:longint;
    tt:array[1..4040] of re;
  end;

var
  t:array[1..4040] of tree;
  ch:char;
  i,j,k,l,m,n,x,y,x1,x2,y1,y2,ans:longint;

procedure build2(left,right,posx,posy:longint);
var
  m:longint;
begin
  t[posx].tt[posy].l:=left;
  t[posx].tt[posy].r:=right;
  t[posx].tt[posy].val:=0;
  if left=right then
    exit;
  m:=(left+right) div 2;
  build2(left,m,posx,posy*2);
  build2(m+1,right,posx,posy*2+1);
end;

procedure build(l,r,pos:longint);
var
  m:longint;
begin
  t[pos].l:=l;
  t[pos].r:=r;
  build2(1,n,pos,1);
  if l=r then
    exit;
  m:=(l+r) div 2;
  build(l,m,pos*2);
  build(m+1,r,pos*2+1);
end;

procedure update2(posx,posy,l,r:longint);
var
  m,a,b:longint;
begin
  if (t[posx].tt[posy].l=l) and (t[posx].tt[posy].r=r) then
    begin
      a:=t[posx].tt[posy].val;
      if a=0 then a:=1
      else a:=0;
      t[posx].tt[posy].val:=a;
      exit;
    end;
  m:=(t[posx].tt[posy].r+t[posx].tt[posy].l) div 2;
  if r<=m then
    update2(posx,posy*2,l,r)
  else
    if l>m then
      update2(posx,posy*2+1,l,r)
    else
      begin
        update2(posx,posy*2,l,m);
        update2(posx,posy*2+1,m+1,r);
      end;
end;

procedure update(pos,x1,y1,x2,y2:longint);
var
  m:longint;
begin
  if (t[pos].l=x1) and (t[pos].r=x2) then
    begin
      update2(pos,1,y1,y2);
      exit;
    end;
  m:=(t[pos].r+t[pos].l) div 2;
  if x1<=m then
    update(pos*2,x1,y1,x2,y2)
  else
    if x1>m then
      update(pos*2+1,x1,y1,x2,y2)
    else
      begin
        update(pos*2,x1,y1,m,y2);
        update(pos*2+1,m+1,y1,x2,y2);
      end;
end;

procedure query2(y,posx,posy:longint);
var
  m:longint;
begin
  ans:=ans xor (t[posx].tt[posy].val);
  if t[posx].tt[posy].l=t[posx].tt[posy].r then
    exit;
  m:=(t[posx].tt[posy].r+t[posx].tt[posy].l) div 2;
  if y>m then
    query2(y,posx,posy*2+1)
  else
    query2(y,posx,posy*2);
end;

procedure query(x,y,pos:longint);
var
  m:longint;
begin
  query2(y,pos,1);
  if t[pos].l=t[pos].r then
    exit;
    m:=(t[pos].r+t[pos].l) div 2;
  if x>m then
    query(x,y,pos*2+1)
  else
    query(x,y,pos*2);
end;

begin
  readln(k);
  while (k>0) do
    begin
      dec(k);
      readln(n,m);
      build(1,n,1);
      while (m>0) do
        begin
          dec(m);
          read(ch);
          if ch='C' then
            begin
              readln(x1,y1,x2,y2);
              update(1,x1,y1,x2,y2);
            end;
          if ch='Q' then
            begin
              readln(x,y);
              ans:=0;
              query(x,y,1);
              writeln(ans);
            end;
        end;
      writeln;
    end;
end.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator