BZOJ 1018 堵塞的交通traffic(线段树)

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1018

题意：一个2*n的格子，相邻格子之间有一条道路。初始时道路是不通的。 三种操作：（1）某条道路连起来；（2）某条道路断开；（3）询问某两个格子是否相连。

思路：（1）首先，线段树的节点保存[L,R]区间两端的四个格子的连通情况，共六种,另外还要保存[L,mid],[mid+1,R]这两段之间的连通情况，即格子(1,mid)和(1,mid+1)以及(2,mid)和(2,mid+1)是否连接；

（2）查询[L,R]时，有可能L直接与R相连，也有可能L向前走再回来，或者R向后走再回来。查询p=[1,L],r=[L,R],q=[R,n]。那么p的右侧两个格子相连或者r的左侧两个格子相连，则r的左侧两个格子相连；q的左侧两个格子相连或者r的右侧两个格子相连，则r的右侧两个格子相连。此时利用r的四个格子的连通情况就可以判断询问的两个格子是否连通。

（3）修改时，x1=x2，则两个格子为同一行相邻格子，否则为同一列的两个格子。

 
 
struct Node
{
    int lb,rb,b[2][2];
};




struct node
{
    int b0,b1,L,R,mid;
    Node b;
};




node a[N<<2];




Node merge(Node a,Node b,int b0,int b1)
{
    Node ans;
    ans.lb=a.lb||(a.b[0][0]&&b0&&b.lb&&b1&&a.b[1][1]);
    ans.rb=b.rb||(b.b[0][0]&&b0&&a.rb&&b1&&b.b[1][1]);
    clr(ans.b,0);
    int i,j;
    if(b0) FOR0(i,2) FOR0(j,2) ans.b[i][j]|=a.b[i][0]&&b.b[0][j];
    if(b1) FOR0(i,2) FOR0(j,2) ans.b[i][j]|=a.b[i][1]&&b.b[1][j];
    return ans;
} 




void build(int t,int L,int R)
{
    a[t].L=L;
    a[t].R=R;
    a[t].mid=(L+R)>>1;
    if(L==R)
    {
        a[t].b.b[0][0]=a[t].b.b[1][1]=1;
        return;
    }
    build(t*2,L,a[t].mid);
    build(t*2+1,a[t].mid+1,R);
}




void update(int t,int x1,int y1,int x2,int y2,int b)
{
    if(x1==x2&&a[t].mid==y1)
    {
        if(x1==0) a[t].b0=b;
        else a[t].b1=b;
        a[t].b=merge(a[t*2].b,a[t*2+1].b,a[t].b0,a[t].b1);
        return;
    }
    if(a[t].L==a[t].R)
    {
        a[t].b.lb=a[t].b.rb=a[t].b.b[0][1]=a[t].b.b[1][0]=b;
        return;
    }
    if(y1<=a[t].mid) update(t*2,x1,y1,x2,y2,b);
    else update(t*2+1,x1,y1,x2,y2,b);
    a[t].b=merge(a[t*2].b,a[t*2+1].b,a[t].b0,a[t].b1);
}








Node query(int t,int L,int R)
{
    if(a[t].L==L&&a[t].R==R) return a[t].b;
    if(R<=a[t].mid) return query(t*2,L,R);
    if(L>a[t].mid) return query(t*2+1,L,R);
    Node p=query(t*2,L,a[t].mid);
    Node q=query(t*2+1,a[t].mid+1,R);
    return merge(p,q,a[t].b0,a[t].b1);
}




int n;




int main()
{
    RD(n); build(1,1,n);
    char op[10];
    int x1,y1,x2,y2;
    Node p,q,r;
    int i,j,ans;
    while(scanf("%s",op),op[0]!='E')
    {
        RD(x1,y1); RD(x2,y2); x1--; x2--;
        if(y1>y2) swap(y1,y2),swap(x1,x2);
        if(op[0]=='C') update(1,x1,y1,x2,y2,0);
        else if(op[0]=='O') update(1,x1,y1,x2,y2,1);
        else
        {
            p=query(1,1,y1);
            q=query(1,y2,n);
            r=query(1,y1,y2);
            if(p.rb) r.lb=1;
            if(q.lb) r.rb=1;
            ans=0;
            FOR0(i,2) FOR0(j,2) if(r.b[i][j])
            {
                if((i==x1||r.lb)&&(j==x2||r.rb)) ans=1;
            }
            if(ans) puts("Y");
            else puts("N");
        }
    }
}