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.2cto.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.
