【bzoj1018】[SHOI2008]堵塞的交通traffic

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

Sample Output

Y
N

【题解】JudgeOnline/upload/201604/sol(4).rar

一道很恶心的线段树维护区间连通性（蒟蒻这才知道线段树可以干这个），不知道怎么维护的看我代码。

注意细节，整整调试了1天才A掉。

——参考文献http://www.cnblogs.com/Cydiater/p/5806133.html

 #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 ;

 }

巴特西