1018: [SHOI2008]堵塞的交通traffic

Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 2252 Solved: 711
[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”作为结束。我们假设在一开始所有的道路都是堵塞的。 对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
Sample Output

Y

N

一道用线段树维护连通性的题。
第一做这种题，其实这类问题我们需要维护一下区间内的联通关系，再用我们维护的这些关系去查询。
对于这道题，我觉得可以有两种建树的方法：
①：以每一列为一个叶子节点。
②：以每一个区间（就是每1条横向道路连接的左右两个节点）为一个叶子节点。
我选择的是第一种，我们首先需要维护6个变量（也就是区间内的6种联通关系），分别是luru，ldrd，lurd，ldru，luld，rurd（l：left；r：right；u：up；d：down）
然后由于还有修改横向相邻的道路，所以我们还要维护一个side[]表示这个节点是否可以向外延伸。
最后就是最麻烦的查询了，需要分很多种情况讨论，尤其是当我们查询的这段区间的联通性需要借助它以外的区间才可以联通的这种情况，这些情况就不一一赘述了，具体的看代码吧。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100100;
struct S{bool luru,ldrd,lurd,ldru,luld,rurd,side[3];}tr[N*4];
char ch[10];
int n,r1,c1,r2,c2;
#define mid (l+r)/2
#define L k<<1,l,mid
#define R k<<1|1,mid+1,r
S update(S x,S y)
{
    S ans;
    ans.side[1]=y.side[1];
    ans.side[2]=y.side[2];
    ans.luru=ans.ldrd=ans.lurd=ans.ldru=ans.luld=ans.rurd=false;
    if((x.luru&&x.side[1]&&y.luru)||(x.lurd&&x.side[2]&&y.ldru)) ans.luru=true;
    if((x.ldrd&&x.side[2]&&y.ldrd)||(x.ldru&&x.side[1]&&y.lurd)) ans.ldrd=true;
    if((x.luru&&x.side[1]&&y.lurd)||(x.lurd&&x.side[2]&&y.ldrd)) ans.lurd=true;
    if((x.ldrd&&x.side[2]&&y.ldru)||(x.ldru&&x.side[1]&&y.luru)) ans.ldru=true;
    if((x.luld)||(x.luru&&x.side[1]&&y.luld&&x.side[2]&&x.ldrd)) ans.luld=true;
    if((y.rurd)||(y.luru&&x.side[1]&&x.rurd&&x.side[2]&&y.ldrd)) ans.rurd=true;
    return ans;
}
void build(int k,int l,int r)
{
    if(l==r){
        tr[k].luru=tr[k].ldrd=true;
        return ;
    }
    build(L);build(R);
    tr[k]=update(tr[k<<1],tr[k<<1|1]);
}
void insert_a(int k,int l,int r,int x,bool kind)
{
    if(l==r){
        tr[k].luld=tr[k].rurd=tr[k].lurd=tr[k].ldru=kind;
        return ;
    }
    if(x<=mid) insert_a(L,x,kind);
    else insert_a(R,x,kind);
    tr[k]=update(tr[k<<1],tr[k<<1|1]);
}
void insert_b(int k,int l,int r,int x,int y,bool kind)
{
    if(l==r){
        tr[k].side[y]=kind;
        return ;
    }
    if(x<=mid) insert_b(L,x,y,kind);
    else insert_b(R,x,y,kind);
    tr[k]=update(tr[k<<1],tr[k<<1|1]);
}
S query(int k,int l,int r,int x,int y)
{
    S ans1,ans2;
    bool left=false,right=false;
    if(x<=l&&y>=r) return tr[k];
    if(x<=mid) ans1=query(L,x,y),left=true;
    if(y>mid) ans2=query(R,x,y),right=true;
    if(right&&left) return update(ans1,ans2);
    else return left?ans1:ans2;
}
bool check()
{
    S now,pre,last;
    if(c1>c2){
        swap(r1,r2);
        swap(c1,c2);
    }
    now=query(1,1,n,c1,c2);
    pre=query(1,1,n,1,c1);
    last=query(1,1,n,c2,n);
    if(r1==r2){
        if((r1==1)&&((now.luru)||(last.luld&&now.lurd)||(pre.rurd&&now.ldru)||(pre.rurd&&now.ldrd&&last.luld))) return true;
        if((r1==2)&&((now.ldrd)||(last.luld&&now.ldru)||(pre.rurd&&now.lurd)||(pre.rurd&&now.luru&&last.luld))) return true;
    }
    else{
        if((r1==1)&&((now.lurd)||(last.luld&&now.luru)||(pre.rurd&&now.ldrd)||(pre.rurd&&now.ldru&&last.luld))) return true;
        if((r1==2)&&((now.ldru)||(last.luld&&now.ldrd)||(pre.rurd&&now.luru)||(pre.rurd&&now.lurd&&last.luld))) return true;
    }
    return false;
}
int main()
{
    int i,j;
    scanf("%d",&n);
    build(1,1,n);
    while(scanf("%*c%s",&ch)){
        if(ch[0]=='E') break;
        scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
        if(ch[0]=='O'){
            if(c1==c2) insert_a(1,1,n,c1,1);
            else insert_b(1,1,n,min(c1,c2),r1,1);
        }
        if(ch[0]=='C'){
            if(c1==c2) insert_a(1,1,n,c1,0);
            else insert_b(1,1,n,min(c1,c2),r1,0);
        }
        if(ch[0]=='A'){
            if(check()) printf("Y\n");
            else printf("N\n");
        }
    }
}