1018: [SHOI2008]堵塞的交通traffic
Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 3242 Solved: 1084
[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;Input
第一行只有一个整数C,表示网格的列数。接下来若干行,每行为一条交通信息,以单独的一行“Exit”作为
结束。我们假设在一开始所有的道路都是堵塞的。我们保证 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
ExitSample Output
Y
N

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 100010 char s[]; struct node
{
int l,r,lc,rc;
bool c11,c12,c21,c22,cl,cr;
}tr[Maxn*]; bool cn[][Maxn],cn2[Maxn]; void upd(int x)
{
if(tr[x].l==tr[x].r) return;
int lc=tr[x].lc,rc=tr[x].rc;
int mid=(tr[x].l+tr[x].r)>>;
tr[x].c11=tr[x].c12=tr[x].c21=tr[x].c22=tr[x].cl=tr[x].cr=;
if(tr[lc].c11&&tr[rc].c11&&cn[][mid]) tr[x].c11=;
if(tr[lc].c12&&tr[rc].c21&&cn[][mid]) tr[x].c11=; if(tr[lc].c11&&tr[rc].c12&&cn[][mid]) tr[x].c12=;
if(tr[lc].c12&&tr[rc].c22&&cn[][mid]) tr[x].c12=; if(tr[lc].c21&&tr[rc].c11&&cn[][mid]) tr[x].c21=;
if(tr[lc].c22&&tr[rc].c21&&cn[][mid]) tr[x].c21=; if(tr[lc].c21&&tr[rc].c12&&cn[][mid]) tr[x].c22=;
if(tr[lc].c22&&tr[rc].c22&&cn[][mid]) tr[x].c22=; if((tr[lc].c11&&tr[lc].c22&&tr[rc].cl&&cn[][mid]&&cn[][mid])||tr[lc].cl) tr[x].cl=;
if((tr[rc].c11&&tr[rc].c22&&tr[lc].cr&&cn[][mid]&&cn[][mid])||tr[rc].cr) tr[x].cr=;
} int tot;
int build(int l,int r)
{
int x=++tot;
tr[x].l=l;tr[x].r=r;
tr[x].c11=tr[x].c12=tr[x].c21=tr[x].c22=tr[x].cl=tr[x].cr=;
if(l!=r)
{
int mid=(l+r)>>;
tr[x].lc=build(l,mid);
tr[x].rc=build(mid+,r);
}
else tr[x].lc=tr[x].rc=,tr[x].c11=tr[x].c22=tr[x].cl=tr[x].cr=;
return x;
} void change(int x,int l,int r)
{
if(tr[x].l==tr[x].r)
{
if(cn2[l]) tr[x].c12=tr[x].c21=tr[x].cl=tr[x].cr=;
else tr[x].c12=tr[x].c21=tr[x].cl=tr[x].cr=;
return;
}
int mid=(tr[x].l+tr[x].r)>>;
if(r<=mid) change(tr[x].lc,l,r);
else if(l>mid) change(tr[x].rc,l,r);
else
{
change(tr[x].lc,l,mid);
change(tr[x].rc,mid+,r);
}
upd(x);
} bool a11,a12,a21,a22,al,ar;
void query(int x,int l,int r)
{
if(tr[x].l==l&&tr[x].r==r)
{
a11=tr[x].c11;
a12=tr[x].c12;
a21=tr[x].c21;
a22=tr[x].c22;
al=tr[x].cl;ar=tr[x].cr;
return;
}
int mid=(tr[x].l+tr[x].r)>>;
if(r<=mid) query(tr[x].lc,l,r);
else if(l>mid) query(tr[x].rc,l,r);
else
{
bool b11,b12,b21,b22,bl,br,c11,c12,c21,c22,cl,cr;
query(tr[x].lc,l,mid);b11=a11;b12=a12;b21=a21;b22=a22;bl=al;br=ar;
query(tr[x].rc,mid+,r);c11=a11;c12=a12;c21=a21;c22=a22;cl=al;cr=ar;
a11=a12=a21=a22=al=ar=;
if(b11&&c11&&cn[][mid]) a11=;
if(b12&&c21&&cn[][mid]) a11=; if(b11&&c12&&cn[][mid]) a12=;
if(b12&&c22&&cn[][mid]) a12=; if(b21&&c11&&cn[][mid]) a21=;
if(b22&&c21&&cn[][mid]) a21=; if(b21&&c12&&cn[][mid]) a22=;
if(b22&&c22&&cn[][mid]) a22=;
if((b11&&b22&&cl&&cn[][mid]&&cn[][mid])||bl) al=;
if((c11&&c22&&br&&cn[][mid]&&cn[][mid])||cr) ar=;
}
} int main()
{
int n;
scanf("%d",&n);
tot=;
build(,n);
for(int i=;i<=n;i++) cn[][i]=cn[][i]=cn2[i]=;
while()
{
scanf("%s",s);
if(s[]=='E') break;
int r1,c1,r2,c2;
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
// if(c1>c2) swap(c1,c2);
if(c1>c2||(c1==c2&&r1>r2))
{
swap(r1,r2);swap(c1,c2);
// int tt;
// tt=r1,r1=r2,r1=tt;
// tt=c1,c1=c2,c2=tt;
}
if(s[]=='O')
{
if(r1==r2) cn[r1-][c1]=;
else cn2[c1]=;
change(,c1,c2);
}
else if(s[]=='C')
{
if(r1==r2) cn[r1-][c1]=;
else cn2[c1]=;
change(,c1,c2);
}
else
{
if(r1==r2&&c1==c2) {printf("Y\n");continue;}
a11=a12=a21=a22=al=ar=;
query(,c1,c2);
if(r1==&&r2==&&a11) printf("Y\n");
else if(r1==&&r2==&&a12) printf("Y\n");
else if(r1==&&r2==&&a21) printf("Y\n");
else if(r1==&&r2==&&a22) printf("Y\n");
else
{
bool b11,b12,b21,b22;
b11=a11;b12=a12;b21=a21;b22=a22;
bool ok=,p1=,p2=;
if(cn[][c1-]&&cn[][c1-])
{
a11=a12=a21=a22=al=ar=;
query(,,c1-);if(ar)
if((r2==&&(b11||b21))||(r2==&&(b12||b22))) {ok=;printf("Y\n");}
if(ar) p1=;
}
if(!ok&&cn[][c2]&&cn[][c2]&&c2<n)
{
a11=a12=a21=a22=al=ar=;
query(,c2+,n);if(al)
if((r1==&&(b11||b12))||(r1==&&(b21||b22))) {ok=;printf("Y\n");}
if(al) p2=;
}
if(!ok&&p1&&p2&&cn[][c1-]&&cn[][c1-]&&cn[][c2]&&cn[][c2]&&c2<n)
{
if(b11||b12||b21||b22) {ok=;printf("Y\n");}
}
if(!ok) printf("N\n");
}
}
}
return ;
}
2017-03-08 13:27:45