bzoj 1018: [SHOI2008]堵塞的交通traffic

.

题意：在一个2*n的网格图上，每次可以删除或添加一条边，询问某两个点的连通性
题解：线段树+二分
一开始想错了，调了一整天。。。
用线段树维护某个区间四个角的连通性，用c[2][2]记录。这样就可以处理出某两个点只经过它们围成矩形里的边能不能到达。但有时候两个点间的路径是不完全在这个矩形里的，所以我们就要处理出询问的两个点到边界最多可以走到哪里，新求出来的两个点间的路径就一定在它们之间（因为没办法再往两边走了）。这个可以用二分来做。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[3][100010];
struct tree
{
    int l,r;
    bool c[2][2];
    tree *lc,*rc;
    tree(int l,int r):l(l),r(r)
    {
        lc=rc=0;
        memset(c,0,sizeof(c));
    }
}*rt;
struct hh
{
    bool a[2][2];
    bool* operator[](int x)
    {
        return a[x];
    }
};
tree* bt(int l,int r)
{
    tree *i=new tree(l,r);
    if(l<r)
    {
        int md=l+r>>1;
        i->lc=bt(l,md);
        i->rc=bt(md+1,r);
    }
    else
    i->c[0][0]=i->c[1][1]=1;
    return i;
}
void pushup(tree *i)
{
    tree *lc=i->lc,*rc=i->rc;
    int md=i->l+i->r>>1;
    i->c[0][0]=lc->c[0][0]&&rc->c[0][0]&&a[1][md]||lc->c[0][1]&&rc->c[1][0]&&a[2][md];
    i->c[0][1]=lc->c[0][0]&&rc->c[0][1]&&a[1][md]||lc->c[0][1]&&rc->c[1][1]&&a[2][md];
    i->c[1][0]=lc->c[1][0]&&rc->c[0][0]&&a[1][md]||lc->c[1][1]&&rc->c[1][0]&&a[2][md];
    i->c[1][1]=lc->c[1][0]&&rc->c[0][1]&&a[1][md]||lc->c[1][1]&&rc->c[1][1]&&a[2][md];
}
void chg(tree *i,int p,int x)
{
    if(i->l==i->r)
    {
        i->c[1][0]=i->c[0][1]=x;
        return;
    }
    int md=i->l+i->r>>1;
    if(p<=md)
    chg(i->lc,p,x);
    else
    chg(i->rc,p,x);
    pushup(i);
}
void upd(tree *i,int p)
{
    if(i->l==i->r)
    return;
    int md=i->l+i->r>>1;
    if(p<=md)
    upd(i->lc,p);
    else
    upd(i->rc,p);
    pushup(i);
}
hh get(tree *i,int y1,int y2)
{
    if(i->l==y1&&i->r==y2)
    {
        hh oo;
        oo[0][0]=i->c[0][0];
        oo[0][1]=i->c[0][1];
        oo[1][0]=i->c[1][0];
        oo[1][1]=i->c[1][1];
        return oo;
    }
    int md=i->l+i->r>>1;
    if(y2<=md)
    return get(i->lc,y1,y2);
    else if(y1>md)
    return get(i->rc,y1,y2);
    else
    {
        hh ll=get(i->lc,y1,md),rr=get(i->rc,md+1,y2);
        hh ans;
        ans[0][0]=ll[0][0]&&rr[0][0]&&a[1][md]||ll[0][1]&&rr[1][0]&&a[2][md];
        ans[0][1]=ll[0][0]&&rr[0][1]&&a[1][md]||ll[0][1]&&rr[1][1]&&a[2][md];
        ans[1][0]=ll[1][0]&&rr[0][0]&&a[1][md]||ll[1][1]&&rr[1][0]&&a[2][md];
        ans[1][1]=ll[1][0]&&rr[0][1]&&a[1][md]||ll[1][1]&&rr[1][1]&&a[2][md];
        return ans;
    }
}
pair<int,int> lmost(int x1,int y1)
{
    int l=1,len=y1;
    while(len)
    {
        int md=l+(len>>1);
        hh oo=get(rt,md,y1);
        if(oo[0][x1]||oo[1][x1])
        len>>=1;
        else
        {
            l=md+1;
            len=len-(len>>1)-1;
        }
    }
    if(l==y1)
    return make_pair(x1,y1);
    else
    {
        hh oo=get(rt,l,y1);
        if(oo[0][x1])
        return make_pair(0,l);
        else
        return make_pair(1,l);
    }
}
pair<int,int> rmost(int x1,int y1)
{
    int l=y1,len=n-y1+1;
    while(len)
    {
        int md=l+(len>>1);
        hh oo=get(rt,y1,md);
        if(oo[x1][0]||oo[x1][1])
        {
            l=md+1;
            len=len-(len>>1)-1;
        }
        else
        len>>=1;
    }
    l--;
    if(l==y1)
    return make_pair(x1,y1);
    else
    {
        hh oo=get(rt,y1,l);
        if(oo[x1][0])
        return make_pair(0,l);
        else
        return make_pair(1,l);
    }
}
int main()
{
    scanf("%d",&n);
    rt=bt(1,n);
    while(1)
    {
        char s[5];
        scanf("%s",s);
        if(s[0]=='E')
        break;
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(s[0]=='O')
        {
            if(x1==x2)
            {
                a[x1][min(y1,y2)]=1;
                upd(rt,min(y1,y2));
            }
            else
            {
                chg(rt,y1,1);
            }
        }
        else if(s[0]=='C')
        {
            if(x1==x2)
            {
                a[x1][min(y1,y2)]=0;
                upd(rt,min(y1,y2));
            }
            else
            {
                chg(rt,y1,0);
            }
        }
        else
        {
            x1--;
            x2--;
            if(y1>y2)
            {
                swap(x1,x2);
                swap(y1,y2);
            }
            pair<int,int>l=lmost(x1,y1),r=rmost(x2,y2);
            hh oo=get(rt,l.second,r.second);
            if(oo[l.first][r.first])
            puts("Y");
            else
            puts("N");
        }
    }
}