1018: [SHOI2008]堵塞的交通traffic
Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 2638 Solved: 864
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”作为结束。我们假设在一开始所有的道路都是堵塞的。 对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
N
思维要缜密啊。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
int n;
bool U[maxn],D[maxn],M[maxn];
bool t[maxn<<][];
bool ret[maxn<<][];
void Push_up(int x){
int l=x<<,r=l|;
t[x][]=(t[l][]&&t[r][])||(t[l][]&&t[r][]);
t[x][]=(t[l][]&&t[r][])||(t[l][]&&t[r][]);
t[x][]=(t[l][]&&t[r][])||(t[l][]&&t[r][]);
t[x][]=(t[l][]&&t[r][])||(t[l][]&&t[r][]);
t[x][]=t[l][]||(t[l][]&&t[l][]&&t[r][]);
t[x][]=t[r][]||(t[r][]&&t[r][]&&t[l][]);
} void Update(int x,int l,int r,int g){
if(l==r){
t[x][]=U[l]||(M[l]&&D[l]&&M[l+]);
t[x][]=D[l]||(M[l]&&U[l]&&M[l+]);
t[x][]=(M[l]&&D[l])||(U[l]&&M[l+]);
t[x][]=(M[l]&&U[l])||(D[l]&&M[l+]);
t[x][]=M[l]||(M[l+]&&U[l]&&D[l]);
t[x][]=M[l+]||(M[l]&&U[l]&&D[l]);
return;
}
int mid=(l+r)>>;
if(mid>=g)Update(x<<,l,mid,g);
else Update(x<<|,mid+,r,g);
Push_up(x);
}
void Query(int x,int l,int r,int a,int b){
if(l>=a&&r<=b){
ret[x][]=t[x][];
ret[x][]=t[x][];
ret[x][]=t[x][];
ret[x][]=t[x][];
ret[x][]=t[x][];
ret[x][]=t[x][];
return;
}
int mid=(l+r)>>;
if(mid>=a)Query(x<<,l,mid,a,b);
if(mid<b)Query(x<<|,mid+,r,a,b);
if(mid>=a&&mid<b){
int ls=x<<,rs=ls|;
ret[x][]=(ret[ls][]&&ret[rs][])||(ret[ls][]&&ret[rs][]);
ret[x][]=(ret[ls][]&&ret[rs][])||(ret[ls][]&&ret[rs][]);
ret[x][]=(ret[ls][]&&ret[rs][])||(ret[ls][]&&ret[rs][]);
ret[x][]=(ret[ls][]&&ret[rs][])||(ret[ls][]&&ret[rs][]);
ret[x][]=ret[ls][]||(ret[ls][]&&ret[ls][]&&ret[rs][]);
ret[x][]=ret[rs][]||(ret[rs][]&&ret[rs][]&&ret[ls][]);
}
else{
if(mid>=a){
ret[x][]=ret[x<<][];
ret[x][]=ret[x<<][];
ret[x][]=ret[x<<][];
ret[x][]=ret[x<<][];
ret[x][]=ret[x<<][];
ret[x][]=ret[x<<][];
}
else{
ret[x][]=ret[x<<|][];
ret[x][]=ret[x<<|][];
ret[x][]=ret[x<<|][];
ret[x][]=ret[x<<|][];
ret[x][]=ret[x<<|][];
ret[x][]=ret[x<<|][];
}
}
}
bool Solve(int x1,int y1,int x2,int y2){
if(y1==y2){
if(x1==x2)return true;
bool re=M[y1];
if(y1<=n){
Query(,,n,y1,n);
re|=ret[][];
}
if(y1>=){
Query(,,n,,y1-);
re|=ret[][];
}
return re;
}
bool t1[],t2[],t3[];
memset(t1,,sizeof(t1));
memset(t3,,sizeof(t3));
if(<=y1-){
Query(,,n,,y1-);
memcpy(t1,ret[],sizeof(ret[]));
}
Query(,,n,y1,y2-);
memcpy(t2,ret[],sizeof(ret[]));
if(y2<=n){
Query(,,n,y2,n);
memcpy(t3,ret[],sizeof(ret[]));
}
if(x1==x2){
if(x1==)
return t2[]||(t1[]&&t2[])||(t3[]&&t2[])||(t1[]&&t2[]&&t3[]);
else
return t2[]||(t1[]&&t2[])||(t3[]&&t2[])||(t1[]&&t2[]&&t3[]);
}
else{
if(x1==)
return t2[]||(t1[]&&t2[])||(t3[]&&t2[]);
else
return t2[]||(t1[]&&t2[])||(t3[]&&t2[]);
}
} int main(){
freopen("traffic.in","r",stdin);
freopen("traffic.out","w",stdout);
int x1,y1,x2,y2;
char op[];
scanf("%d",&n);n--;
while(true){
scanf("%s",op);
if(!strcmp(op,"Exit"))break;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(y1>y2){swap(x1,x2);swap(y1,y2);}
if(!strcmp(op,"Close")){
if(x1==x2)
if(x1==)U[y1]=false;
else D[y1]=false;
else M[y1]=false;
Update(,,n,y1);
if(y1!=y2)Update(,,n,y2);
if(y1-)Update(,,n,y1-);
}
else if(!strcmp(op,"Open")){
if(x1==x2)
if(x1==)
U[y1]=true;
else
D[y1]=true;
else
M[y1]=true;
Update(,,n,y1);
if(y1!=y2)Update(,,n,y2);
if(y1-)Update(,,n,y1-);
}
else if(!strcmp(op,"Ask"))
printf("%c\n",Solve(x1,y1,x2,y2)?'Y':'N');
}
return ;
}