BZOJ-1018: [SHOI2008]堵塞的交通traffi

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1018

用线段树维护区间的连通性，对于一个区间[L,R]，维护的连通性如下图中加粗的连边表示：

0bd162d9f2d3572c0e5baf618813632763d0c3d5.jpg.png

然后就各种DT的分类讨论合并啦~

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define update( t ) I( t )=I(left( t ))+I(right( t ))

 

#define L( t ) L[ t ]

#define R( t ) R[ t ]

#define I( t ) I[ t ]

 

#define left( t )( t <<1)

#define right( t )(left( t )^1)

 

#define maxv ( maxn <<2)

#define maxn 100100

 

struct itype{

    int l , r ;

    bool f[6];

    itype(  ){

        memset( f ,false,sizeof( f ));

    }

};

 

bool road[ maxn ][3];

 

itype operator+(const itype &l ,const itype &r ){

    itype rec ;

    rec.l = l.l , rec.r = r.r ;

    rec.f[0]= l.f[0]||((( l.f[1]&& l.f[3])||( l.f[4]&& l.f[5]))&& road[ l.r ][0]&& road[ l.r ][1]&& r.f[0]);

    rec.f[1]=( l.f[1]&& road[ l.r ][0]&& r.f[1])||( l.f[4]&& road[ l.r ][1]&& r.f[5]);

    rec.f[2]= r.f[2]||((( r.f[1]&& r.f[3])||( r.f[4]&& r.f[5]))&& road[ l.r ][0]&& road[ l.r ][1]&& l.f[2]);

    rec.f[3]=( l.f[3]&& road[ l.r ][1]&& r.f[3])||( l.f[5]&& road[ l.r ][0]&& r.f[4]);

    rec.f[4]=( l.f[1]&& road[ l.r ][0]&& r.f[4])||( l.f[4]&& road[ l.r ][1]&& r.f[3]);

    rec.f[5]=( l.f[3]&& road[ l.r ][1]&& r.f[5])||( l.f[5]&& road[ l.r ][0]&& r.f[1]);

    return rec ;

}

 

int L[ maxv ], R[ maxv ];

itype I[ maxv ];

 

void build(int l ,int r ,int t ){

    L( t )= l ,R( t )= r ;

    if( l == r ){

        I( t ).f[1]=I( t ).f[3]=true,I( t ).l =I( t ).r = l ;

        return;

    }

    int mid =( l + r )>>1;

    build( l , mid ,left( t )),build( mid +1, r ,right( t ));

    update( t );

}

 

void change(int x ,int t ){

    if(L( t )==R( t )){

        I( t ).f[1]=I( t ).f[3]=true;

        I( t ).f[0]=I( t ).f[2]=I( t ).f[4]=I( t ).f[5]= road[L( t )][2];

        return;

    }

    int mid =(L( t )+R( t ))>>1;

    change( x , x <= mid ?left( t ):right( t ));

    update( t );

}

 

itype query(int l ,int r ,int t ){

    if( l ==L( t )&& r ==R( t ))return I( t );

    int mid =(L( t )+R( t ))>>1;

    if( r <= mid )return query( l , r ,left( t ));

    if( l > mid )return query( l , r ,right( t ));

    return query( l , mid ,left( t ))+query( mid +1, r ,right( t ));

}

 

int n ;

 

void Change(int x0 ,int y0 ,int x1 ,int y1 ,bool flag ){

    if( y0 > y1 )swap( x0 , x1 ),swap( y0 , y1 );

    if( x0 == x1 ){

        if( x0 ==1) road[ y0 ][0]= flag ;else road[ y0 ][1]= flag ;

    }else road[ y0 ][2]= flag ;

    change( y0 ,1);

}

 

bool Query(int x0 ,int y0 ,int x1 ,int y1 ){

    if( y0 > y1 )swap( x0 , x1 ),swap( y0 , y1 );

    itype templ =query(1, y0 ,1), tempm =query( y0 , y1 ,1), tempr =query( y1 , n ,1);

    if( x0 == x1 ){

        if( x0 ==1){

            if( tempm.f[1])return true;

            if((( templ.f[2]|| tempm.f[0])&&( tempr.f[0]|| tempm.f[2]))&& tempm.f[3])return true;

        }else{

            if( tempm.f[3])return true;

            if((( templ.f[2]|| tempm.f[0])&&( tempr.f[0]|| tempm.f[2]))&& tempm.f[1])return true;

        }

    }else{

        if( x0 ==1){

           if( tempm.f[4])return true;

            if( templ.f[2]&& tempm.f[3])return true;

            if( tempr.f[0]&& tempm.f[1])return true;

            if(( templ.f[2]|| tempm.f[0])&&( tempr.f[0]|| tempm.f[2])&& tempm.f[5])return true;

        }else{

            if( tempm.f[5])return true;

            if( templ.f[2]&& tempm.f[1])return true;

            if( tempr.f[0]&& tempm.f[3])return true;

            if(( templ.f[2]|| tempm.f[0])&&( tempr.f[0]|| tempm.f[2])&& tempm.f[4])return true;

        }

    }

    return false;

}

 

int main(  ){

    memset( road ,false,sizeof( road ));

    scanf("%d",&n );

    build(1, n ,1);

    char s[10];

    for(scanf("%s", s ); s[0]!='E';scanf("%s", s )){

        int x0 , y0 , x1 , y1 ;scanf("%d%d%d%d",&x0 ,&y0 ,&x1 ,&y1 );

        if( s[0]=='C'){

            Change( x0 , y0 , x1 , y1 ,false);

        }else if( s[0]=='O'){

            Change( x0 , y0 , x1 , y1 ,true);

        }else{

            printf(Query( x0 , y0 , x1 , y1 )?"Y\n":"N\n");

        }

    }

    return 0;

}