1018: [SHOI2008]堵塞的交通traffic
Time Limit: 3 Sec Memory Limit:
162 MB
Submit: 617 Solved: 165
[Submit][Status][Discuss]
Description
有一天，由于某种穿越现象作用，你来到了传说中的小人国。小人国的布局非常奇特，整个国家的交通系统可以被看成是一个2行C列的矩形网格，网格上的每个点代表一个城市，相邻的城市之间有一条道路，所以总共有2C个城市和3C-2条道路。 小人国的交通状况非常槽糕。有的时候由于交通堵塞，两座城市之间的道路会变得不连通，直到拥堵解决，道路才会恢复畅通。初来咋到的你决心毛遂自荐到交通部某份差事，部长听说你来自一个科技高度发达的世界，喜出望外地要求你编写一个查询应答系统，以挽救已经病入膏肓的小人国交通系统。
小人国的交通部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式： Close r1 c1 r2 c2：相邻的两座城市(r1,c1)和(r2,c2)之间的道路被堵塞了； Open r1 c1 r2 c2：相邻的两座城市(r1,c1)和(r2,c2)之间的道路被疏通了； Ask r1 c1 r2 c2：询问城市(r1,c1)和(r2,c2)是否连通。如果存在一条路径使得这两条城市连通，则返回Y，否则返回N；
小人国的交通部将提供一些交通信息给你，你的任务是根据当前的交通情况回答查询的问题。交通信息可以分为以下几种格式： Close r1 c1 r2 c2：相邻的两座城市(r1,c1)和(r2,c2)之间的道路被堵塞了； Open r1 c1 r2 c2：相邻的两座城市(r1,c1)和(r2,c2)之间的道路被疏通了； Ask r1 c1 r2 c2：询问城市(r1,c1)和(r2,c2)是否连通。如果存在一条路径使得这两条城市连通，则返回Y，否则返回N；
Input
第一行只有一个整数C，表示网格的列数。接下来若干行，每行为一条交通信息，以单独的一行“Exit”作为结束。我们假设在一开始所有的道路都是堵塞的。 对30%测试数据，我们保证C小于等于1000，信息条数小于等于1000； 对100%测试数据，我们保证 C小于等于100000，信息条数小于等于100000。
Output
对于每个查询，输出一个“Y”或“N”。
Sample Input
2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit
Sample Output
Y
N
线段树维护连通性……
需要注意联通可能绕一大圈联通= =，一开始没想到挂到死……ORZ
program bzoj1018;
type
group=array [0..5] of boolean;
pair=array [0..1] of boolean;
var
tot,c,i,j,k,x1,y1,x2,y2:longint;
ans:boolean;
ch:char;
x,y,z:group;
left,right:array [0..200001] of longint;
stu:array [0..200001] of group;
www:array [0..200001]of pair;
procedure swap (var a,b:longint);
begin
if a=b then exit;
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
procedure build (s,e,now:longint);
var
mid:longint;
begin
if s=e then
begin
stu[now][0]:=true;
stu[now][3]:=true;
exit;
end;
mid:=(s+e) div 2;
inc(tot);
left[now]:=tot;
build(s,mid,tot);
inc(tot);
right[now]:=tot;
build(mid+1,e,tot);
end;
function update (a,b:group;www:pair):group;
var
i,j,k:longint;
now:group;
begin
fillchar(now,sizeof(now),false);
if www[0] and a[0] and b[0] then now[0]:=true;
if www[1] and a[1] and b[2] then now[0]:=true;
if www[0] and a[0] and b[1] then now[1]:=true;
if www[1] and a[1] and b[3] then now[1]:=true;
if www[0] and a[2] and b[0] then now[2]:=true;
if www[1] and a[3] and b[2] then now[2]:=true;
if www[0] and a[2] and b[1] then now[3]:=true;
if www[1] and a[3] and b[3] then now[3]:=true;
if a[4] then now[4]:=true;
if a[0] and a[3] and www[0] and www[1] and b[4] then now[4]:=true;
if b[5] then now[5]:=true;
if b[0] and b[3] and www[0] and www[1] and a[5] then now[5]:=true;
exit(now);
end;
procedure insertl (w:boolean;x,l,r,now:longint);
var
mid:longint;
begin
if l=r then
begin
if w then
fillchar(stu[now],sizeof(stu[now]),true)
else
begin
fillchar(stu[now],sizeof(stu[now]),false);
stu[now][0]:=true;
stu[now][3]:=true;
end;
exit;
end;
mid:=(l+r) div 2;
if x<=mid then insertl(w,x,l,mid,left[now])
else insertl(w,x,mid+1,r,right[now]);
stu[now]:=update(stu[left[now]],stu[right[now]],www[now]);
end;
procedure insertr (w:boolean;x,y,l,r,now:longint);
var
mid:longint;
begin
mid:=(l+r) div 2;
if x=mid then
begin
www[now][y]:=w;
stu[now]:=update(stu[left[now]],stu[right[now]],www[now]);
exit;
end;
if x<=mid then insertr(w,x,y,l,mid,left[now])
else insertr(w,x,y,mid+1,r,right[now]);
stu[now]:=update(stu[left[now]],stu[right[now]],www[now]);
end;
function find (x1,x2,l,r,now:longint):group;
var
temp:group;
mid:longint;
begin
if (x1=l)and(x2=r) then exit(stu[now]);
mid:=(l+r) div 2;
if x2<=mid then exit(find(x1,x2,l,mid,left[now]))
else
if x1>mid then exit(find(x1,x2,mid+1,r,right[now]))
else exit(
update(find(x1,mid,l,mid,left[now]),
find(mid+1,x2,mid+1,r,right[now]),
www[now])
);
end;
begin
readln(c);
build(1,c,0);
repeat
read(ch);
case ch of
'E':break;
'O':begin
read(ch,ch,ch,y1,x1,y2,x2);
dec(y1);
dec(y2);
if x1=x2 then insertl(true,x1,1,c,0)
else
if x1<x2 then insertr(true,x1,y1,1,c,0)
else insertr(true,x2,y1,1,c,0);
end;
'C':begin
read(ch,ch,ch,ch,y1,x1,y2,x2);
dec(y1);
dec(y2);
if x1=x2 then insertl(false,x1,1,c,0)
else
if x1<x2 then insertr(false,x1,y1,1,c,0)
else insertr(false,x2,y1,1,c,0);
end;
'A':begin
read(ch,ch,y1,x1,y2,x2);
dec(y1);
dec(y2);
if x1>x2 then
begin
swap(x1,x2);
swap(y1,y2);
end;
x:=find(1,x1,1,c,0);
y:=find(x1,x2,1,c,0);
z:=find(x2,c,1,c,0);
ans:=false;
ans:=ans or y[y1*2+y2];
ans:=ans or (x[5] and y[(1-y1)*2+y2]);
ans:=ans or (z[4] and y[y1*2+1-y2]);
ans:=ans or (x[5] and z[4] and y[(1-y1)*2+1-y2]);
if ans then writeln('Y')
else writeln('N');
end;
end;
until false;
end.