1018: [SHOI2008]堵塞的交通traffic
Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 2887 Solved: 954
[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
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
一道很恶心的线段树维护区间连通性（蒟蒻这才知道线段树可以干这个），不知道怎么维护的看我代码。
注意细节，整整调试了1天才A掉。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
const int MAXN=;
struct node
{
bool luru,lurd,luld,rurd,ldru,ldrd;
}tr[MAXN*];
char ch[];
int n,k,v,limleft,limright,toright[][MAXN];
inline int read()
{
int x=,f=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
void build(int p,int l,int r)
{
if(l>r) return;
if(l==r)
{
tr[p].luru=tr[p].ldrd=;
return;
}
int mid=(l+r)/;
build(p*,l,mid);
build(p*+,mid+,r);
}
node merge(node a,node b,int upedge,int downedge)
{
node c;
c.luld=a.luld; c.rurd=b.rurd;
c.luru=(a.luru&upedge&b.luru)|(a.lurd&downedge&b.ldru);
c.ldrd=(a.ldrd&downedge&b.ldrd)|(a.ldru&upedge&b.lurd);
c.lurd=(c.luru&c.rurd)|(c.luld&c.ldrd)|(a.luru&upedge&b.lurd)|(a.lurd&downedge&b.ldrd);
c.ldru=(c.luld&c.luru)|(c.ldrd&c.rurd)|(a.ldru&upedge&b.luru)|(a.ldrd&downedge&b.ldru);
c.luld=c.luld|(c.lurd&c.ldrd)|(c.ldru&c.luru)|(a.luru&upedge&b.luld&downedge&a.ldrd);
c.rurd=c.rurd|(c.lurd&c.luru)|(c.ldru&c.ldrd)|(b.luru&upedge&a.rurd&downedge&b.ldrd);
return c;
}
void updata1(int p,int l,int r)
{
if(l>k||r<k) return;
if(l==k&&r==k)
{
tr[p].luld=tr[p].rurd=tr[p].lurd=tr[p].ldru=v;
return;
}
int mid=(l+r)/;
updata1(p*,l,mid);
updata1(p*+,mid+,r);
tr[p]=merge(tr[p*],tr[p*+],toright[][mid],toright[][mid]);
}
void updata2(int p,int l,int r)
{
if(l>k||r<k) return;
if(l==k&&r==k) return;
int mid=(l+r)/;
updata2(p*,l,mid);
updata2(p*+,mid+,r);
tr[p]=merge(tr[p*],tr[p*+],toright[][mid],toright[][mid]);
}
node get(int p,int l,int r)
{
node a,b,c;
if(l>=limleft&&r<=limright) return tr[p];
int mid=(l+r)/;
if(mid+<=limleft) return get(p*+,mid+,r);
else if(limright<=mid) return get(p*,l,mid);
else
{
a=get(p*,l,mid);
b=get(p*+,mid+,r);
c=merge(a,b,toright[][mid],toright[][mid]);
}
return c;
}
int main()
{
//freopen("bzoj_1018.in","r",stdin);
//freopen("bzoj_1018.out","w",stdout);
n=read();
build(,,n);
while(scanf("%s",ch+))
{
if(ch[]=='E') break;
if(ch[]=='O')
{
int x1=read(),y1=read(),x2=read(),y2=read();
if(y1==y2&&x1!=x2)
{
k=y1; v=;
updata1(,,n);
}
if(x1==x2&&y1!=y2)
{
y1=min(y1,y2); k=y1;
toright[x1-][y1]=; updata2(,,n);
}
}
if(ch[]=='C')
{
int x1=read(),y1=read(),x2=read(),y2=read();
if(y1>y2) {swap(x1,x2); swap(y1,y2);}
if(y1==y2&&x1!=x2)
{
k=y1; v=;
updata1(,,n);
}
if(x1==x2&&y1!=y2)
{
y1=min(y1,y2); k=y1;
toright[x1-][y1]=; updata2(,,n);
}
}
if(ch[]=='A')
{
int x1=read(),y1=read(),x2=read(),y2=read();
if(x1==x2&&y1==y2) printf("Y\n");
if(y1>y2) {swap(x1,x2); swap(y1,y2);}
limleft=; limright=y1; node Left=get(,,n);
limleft=y1; limright=y2; node Mid=get(,,n);
limleft=y2; limright=n; node Right=get(,,n);
if(y1==y2&&x1!=x2)
{
if(Left.rurd||Mid.luld||Right.luld) printf("Y\n");
else printf("N\n");
}
if(x1==x2&&y1!=y2)
{
if(x1==)
{
if((Left.rurd&&Mid.ldrd&&Right.luld)||Mid.luru||(Left.rurd&&Mid.ldru)||(Mid.lurd&&Right.luld)) printf("Y\n");
else printf("N\n");
}
else
{
if((Left.rurd&&Mid.luru&&Right.luld)||Mid.ldrd||(Left.rurd&&Mid.lurd)||(Mid.ldru&&Right.luld)) printf("Y\n");
else printf("N\n");
}
}
if(x1!=x2&&y1!=y2)
{
if(x1==)
{
if((Left.rurd&&Mid.ldru&&Right.luld)||Mid.lurd||(Left.rurd&&Mid.ldrd)||(Mid.luru&&Right.luld)) printf("Y\n");
else printf("N\n");
}
else
{
if((Left.rurd&&Mid.lurd&&Right.luld)||Mid.ldru||(Left.rurd&&Mid.luru)||(Mid.ldrd&&Right.luld)) printf("Y\n");
else printf("N\n");
}
}
}
}
return ;
}