内容目录
|
Language:
Matrix
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
第一行为数据组数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
|
这题是二维的线段树，
先建一棵线段树，再将它的所有结点（包括根）建立一个二叉树（维护这个结点）
异或仅需记录标记某点所对应的区间取反
查找时统计共记了几个标记即可（标记永久化）
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.