bzoj千题计划108：bzoj1018: [SHOI2008]堵塞的交通traffic

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

#define ok { puts("Y"); continue; }

using namespace std;

#define N 100001

int L[N<<2],R[N<<2];

struct node
{
    bool a[6],b[2];
    void clear() { memset(a,false,sizeof(a)); memset(b,false,sizeof(b)); }
    node operator + (node p) const
    {
        node tmp;
        tmp.clear();
    
        tmp.a[0]=a[0];
        tmp.a[0]|=a[1]&&a[3]&&b[0]&&b[1]&&p.a[0];
    //    cout<<tmp.a[0];
        tmp.a[1]=a[1]&&b[0]&&p.a[1];
        tmp.a[1]|=a[5]&&b[1]&&p.a[4];
    //    cout<<tmp.a[1];
        tmp.a[2]=p.a[2]; 
        tmp.a[2]|=p.a[1]&&p.a[3]&&b[0]&&b[1]&&a[2];
    //    cout<<tmp.a[2];
        tmp.a[3]=a[3]&&b[1]&&p.a[3];
        tmp.a[3]|=a[4]&&b[0]&&p.a[5];
    //    cout<<tmp.a[3];
        tmp.a[4]=a[4]&&b[0]&&p.a[1];
        tmp.a[4]|=a[3]&&b[1]&&p.a[4];
    //    cout<<tmp.a[4];
        tmp.a[5]=a[1]&&b[0]&&p.a[5];
        tmp.a[5]|=a[5]&&b[1]&&p.a[3];
    //    cout<<tmp.a[5];
        tmp.b[0]=p.b[0]; tmp.b[1]=p.b[1];
        
        return tmp;
    }
};

node tr[N<<2];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-‘0‘; c=getchar(); }
}

void build(int k,int l,int r)
{
    L[k]=l; R[k]=r;
    if(l==r) 
    {
        tr[k].a[1]=tr[k].a[3]=true;
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}

void change(int k,int pos,bool ty,int line,bool how)
{
    if(L[k]==R[k])
    {
        if(!ty)
        {
            if(line==1) 
            {
                tr[k].b[0]=how;
                if(tr[k].b[0] && tr[k].a[0]) tr[k].a[5]=true;
                else if(!tr[k].a[0]) tr[k].a[5]=false;
            }
            else 
            {
                tr[k].b[1]=how;
                if(tr[k].b[1] && tr[k].a[0]) tr[k].a[4]=true;
                else if(!tr[k].a[0]) tr[k].a[4]=false;
            }
        }
        else 
        {
            tr[k].a[0]=tr[k].a[2]=how;
            tr[k].a[4]=tr[k].a[5]=how;
        }
        return;
    }
    int mid=L[k]+R[k]>>1;
    if(pos<=mid) change(k<<1,pos,ty,line,how);
    else change(k<<1|1,pos,ty,line,how);
    tr[k]=tr[k<<1]+tr[k<<1|1];
}

node query(int k,int l,int r)
{
    if(L[k]>=l && R[k]<=r) return tr[k];
    int mid=L[k]+R[k]>>1;
    if(r<=mid) return query(k<<1,l,r);
    if(l>mid) return query(k<<1|1,l,r);
    node ll=query(k<<1,l,r),rr=query(k<<1|1,l,r);
    return ll+rr;
}

int main()
{
//    freopen("bzoj_1018.in","r",stdin);
//    freopen("bzoj_1018.out","w",stdout);
    int n; read(n);
    build(1,1,n);
    char c[7];
    int lx,ly,rx,ry;
    int cnt=0;
    while(scanf("%s",c)!=EOF)
    {
        if(c[0]==‘E‘) return 0;
        read(lx); read(ly); read(rx); read(ry);
        if(ly>ry) swap(lx,rx),swap(ly,ry);
        if(c[0]==‘O‘ || c[0]==‘C‘)
        {
            if(lx==rx) change(1,ly,0,lx,c[0]==‘O‘);
            else change(1,ly,1,lx,c[0]==‘O‘);
        }
        else
        {
            node tmp=query(1,ly,ry);
            
            if(ly==ry && tmp.a[0]) ok
            else if(ly!=ry) 
            {
                if(lx==1 && rx==1 && tmp.a[1]) ok
                if(lx==2 && rx==2 && tmp.a[3]) ok
                if(lx==1 && rx==2 && tmp.a[5]) ok
                if(lx==2 && rx==1 && tmp.a[4]) ok
            }
            node l=query(1,1,ly);
            node r=query(1,ry,n);
            if(lx==1 && rx==1)
            {
                if(l.a[2]&&tmp.a[4]) ok
                if(r.a[0]&&tmp.a[5]) ok
                if(l.a[2]&&r.a[0]&&tmp.a[3]) ok
            }
            else if(lx==1 && rx==2)
            {
                if(l.a[2]&&tmp.a[3]) ok
                if(r.a[0]&&tmp.a[1]) ok
                if(l.a[2]&&r.a[0]&&tmp.a[4]) ok
            }
            else if(lx==2 && rx==1)
            {
                if(l.a[2]&&tmp.a[1]) ok
                if(r.a[0]&&tmp.a[3]) ok
                if(l.a[2]&&r.a[0]&&tmp.a[5]) ok
            }
            else
            {
                if(l.a[2]&&tmp.a[5]) ok
                if(r.a[0]&&tmp.a[4]) ok
                if(l.a[2]&&r.a[0]&&tmp.a[1]) ok
            }
            puts("N");
        }
    }
}