POJ 2155(二维zkw线段树）

Matrix
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 13137 Accepted: 4948
Description
给定一个矩阵（初始为0），维护2个操作：
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) ,以(x1,y1)为左上角，(x2,y2)为右上角的矩阵取反。
2. Q x y (1 <= x, y <= n) 输出(x,y)的状态
Input www.zzzyk.com
第一行为数据组数X (X <= 10)
每组数据第一行为N,T (2 <= N <= 1000, 1 <= T <= 50000) 表示矩阵边长与操作次数。
接下来T行，为Q或C操作
Output
请输出所有提问结果。
每组数据后一回车。
Sample Input
1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1
Sample Output
1
0
0
1
Source
POJ Monthly,Lou Tiancheng
这题是二维的线段树，
先建一棵线段树，再将它的所有结点（包括根）建立一个二叉树（维护这个结点）
异或仅需记录标记某点所对应的区间取反
查找时统计共记了几个标记即可（标记永久化）

[delphi]
Program Matrix;
const
   maxtt=10;
   maxn=1000;
   maxMM=50000;
var
   tt,n,mm,i,j,k,x1,y1,x2,y2,x,y,p1,p2,ans:longint;
   c:char;
   t:array[1..5000,1..5000] of boolean;
   M:longint;

Procedure change_y(x,y1,y2:longint);
var
   i,j:longint;
begin
   dec(y1);inc(y2);
   inc(y1,M);inc(y2,M);
   while ((y1 xor y2 xor 1)>0) do
   begin
      if ((y1 and 1)=0) then t[x,y1+1]:=not(t[x,y1+1]);
      if ((y2 and 1)=1) then t[x,y2-1]:=not(t[x,y2-1]);
      y1:=y1 shr 1;y2:=y2 shr 1;
   end;

end;

Procedure change_x(x1,y1,x2,y2:longint);
var
   i,j:longint;
begin
   dec(x1);inc(x2);
   inc(x1,M);inc(x2,M);
   while ((x1 xor x2 xor 1)>0) do
   begin
      if ((x1 and 1)=0) then change_y(x1+1,y1,y2);
      if ((x2 and 1)=1) then change_y(x2-1,y1,y2);
      x1:=x1 shr 1;x2:=x2 shr 1;
   end;
end;

function find_y(x,y:longint):boolean;
var
   i,j:longint;
begin
   inc(y,M); find_y:=false;
   while (y>0) do
   begin
      if (t[x,y]) then find_y:=not(find_y);
      y:=y shr 1;
   end;

end;
function find_x(x,y:longint):boolean;
var
   i,j:longint;
begin
   inc(x,M); find_x:=false;
   while (x>0) do
   begin
      find_x:=find_x xor find_y(x,y);
      x:=x shr 1;
   end;
end;
begin
   readln(tt);
   while (tt>0) do
   begin
      fillchar(t,sizeof(t),false);
      readln(n,mm);
      M:=1;
      while (M-2<n) do M:=M shl 1;
      for k:=1 to mm do
      begin
         read(c);
         if c='C' then
         begin
            readln(x1,y1,x2,y2);
            change_x(x1,y1,x2,y2);

         end
         else
         begin     //Q
            readln(x1,y1);
            if (find_x(x1,y1)) then writeln('1') else writeln('0');

         end;

      end;
      dec(tt);
      if (tt>0) then writeln;
   end;
end.

补充：软件开发 , C++ ,